给定一列数，如果三个或以上的数满足等差数列定义，则称为arithmetic subsequences，问给定的一列数有多少个arithmetic subsequences
1 <= nums.length <= 1000
-231 <= nums[i] <= 231 - 1
这题按照思路来说，大概是Medium难度的DP，用python也特别方便好写，于是闲聊无视非要用C写了一遍，就真的变Hard模式了，搞了n次才AC，发现果然没有别人用C来写。。= =||
总的思路：dp[i][dif]保存处理到第i个数，且相邻数差值为dif的子数列个数，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语言版，思路同上，但因为C里面没有好用的dict，所以用了Hash，LeetCode支持uthash，另外如果直接hash，那么dif的可能性会非常大（cnt保存所有dif的可能性数量），dp数组没法开那么大，于是，只保存真的形成了3个或以上数字的等差数列的dif值（用cnt2来保存符合这样条件的dif值的数量），在开dp数组的时候第二维开多大也有一点小trick
交上去的结果：
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 }