給定一列數(shù)，如果三個(gè)或以上的數(shù)滿足等差數(shù)列定義，則稱為arithmetic subsequences，問(wèn)給定的一列數(shù)有多少個(gè)arithmetic subsequences
1 <= nums.length <= 1000
-231 <= nums[i] <= 231 - 1
這題按照思路來(lái)說(shuō)，大概是Medium難度的DP，用python也特別方便好寫，于是閑聊無(wú)視非要用C寫了一遍，就真的變Hard模式了，搞了n次才AC，發(fā)現(xiàn)果然沒(méi)有別人用C來(lái)寫。。= =||
總的思路：dp[i][dif]保存處理到第i個(gè)數(shù)，且相鄰數(shù)差值為dif的子數(shù)列個(gè)數(shù)，dp更新：
for i in range(len(nums)):
for j in range(i):
dif = nums[j] - nums[i]
dp[i][dif] += dp[j][dif] + 1
ans += dp[j][dif]
Python很好寫，用dict保存所有可能的dif值就行：
1 #446
2 #Runtime: 2028 ms
3 #Memory Usage: 74.3 MB
4
5 class Solution(object):
6 def numberOfArithmeticSlices(self, nums):
7 """
8 :type nums: List[int]
9 :rtype: int
10 """
11 dp = [defaultdict(int) for _ in range(len(nums))]
12 ans = 0
13 for i in range(len(nums)):
14 for j in range(i):
15 dif = nums[j] - nums[i]
16 dp[i][dif] += dp[j][dif] + 1
17 ans += dp[j][dif]
18 return ans
C語(yǔ)言版，思路同上，但因?yàn)镃里面沒(méi)有好用的dict，所以用了Hash，LeetCode支持uthash，另外如果直接hash，那么dif的可能性會(huì)非常大（cnt保存所有dif的可能性數(shù)量），dp數(shù)組沒(méi)法開(kāi)那么大，于是，只保存真的形成了3個(gè)或以上數(shù)字的等差數(shù)列的dif值（用cnt2來(lái)保存符合這樣條件的dif值的數(shù)量），在開(kāi)dp數(shù)組的時(shí)候第二維開(kāi)多大也有一點(diǎn)小trick
交上去的結(jié)果：
Runtime: 799 ms, faster than 100.00% of C online submissions for Arithmetic Slices II - Subsequence.
Memory Usage: 240.9 MB, less than 100.00% of C online submissions for Arithmetic Slices II - Subsequence.
Accepted Solutions Runtime Distribution
Sorry. We do not have enough accepted submissions to show distribution chart.
Accepted Solutions Memory Distribution
Sorry. We do not have enough accepted submissions to show distribution chart.
Invite friends to challenge Arithmetic Slices II - Subsequence
1 //446
2 //Runtime: 799 ms
3 //Memory Usage: 240.9 MB
4
5 struct hashTable {
6 long long key;
7 int val;
8 int init;
9 UT_hash_handle hh;
10 };
11
12 struct hashTable* dict;
13
14 struct hashTable* find(long long k) {
15 struct hashTable* t;
16 HASH_FIND(hh, dict, &k, sizeof(long long), t);
17 return t;
18 }
19
20 int min(int a, int b) {
21 return a<b?a:b;
22 }
23
24 void insert(long long k, int v, int id) {
25 struct hashTable* t = malloc(sizeof(struct hashTable));
26 t->key = k;
27 t->val = v;
28 t->init = id;
29 HASH_ADD(hh, dict, key, sizeof(long long), t);
30 }
31
32 int numberOfArithmeticSlices(int* nums, int numsSize){
33 int ans = 0;
34 int cnt = 0;
35 int idx[numsSize*numsSize];
36 int cnt2 = 0;
37 int dp[numsSize][min(numsSize*numsSize,(int)10000000/numsSize)];
38 memset(dp, 0, sizeof(dp));
39 memset(idx, -1, sizeof(idx));
40 dict = NULL;
41 for(int i = 0; i < numsSize; ++i) {
42 for(int j = 0; j < i; ++j) {
43 long long dif = (long long)nums[j] - (long long)nums[i];
44 struct hashTable* it = find(dif);
45 if(it == NULL) {
46 insert(dif, cnt, i);
47 ++cnt;
48 }
49 else {
50 if(idx[it->val] == -1) {
51 idx[it->val] = cnt2;
52 dp[it->init][cnt2] = 1;
53 dp[i][cnt2] += dp[j][cnt2] + 1;
54 ans += dp[j][cnt2];
55 ++cnt2;
56 }
57 else {
58 dp[i][idx[it->val]] += dp[j][idx[it->val]] + 1;
59 ans += dp[j][idx[it->val]];
60 }
61 }
62
63 }
64 }
65 return ans;
66 }