时间复杂度

O(n): 左右标记都最多移动 n 次

连续子区间和

窗口内的元素之和，大于给定值时，则窗口右标及之后的子数组都应该算在结果中

不能统计左下标及之前的个数，因为窗口之和可能远大于给定值，之后向后滑动时，会重复统计：

数组： 2 4 7 和：6

[2, 2] -> 0

[2, 4] -> 1

[4, 4] -> 0

[4, 7] -> 2

[7,7] -> 3

有重复统计

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include <vector>
#include <iostream>
using namespace std;

long long f(vector<int> &v, long long sum) {
    if(v.size() == 0) {
        return 0;
    }
    
    long long res = 0;
    int l = 0; 
    int r = 0;
    long long s = v[0];
    while(l < v.size()) {
        if(s < sum) {
            if(r + 1 >= v.size()) {
                break;
            }
            r++;
            s += v[r];
            continue;
        }
        if(s >= sum) {
            res += v.size() - r;
            s -= v[l];
            l++;
        }
    }
    
    return res;
}

int main() {
    int c;
    int x;
    cin >> c >> x;
    
    vector<int> v;
    for(int i = 0; i < c; i++) {
        int k;
        cin >> k;
        v.push_back(k);
    }
    cout << f(v, x) << endl;
    return 0;
}

3Sum

排序后，求两数之和等于相反值。

窗口：如果两数之和大于相反值，窗口减少，否则窗口增加

时间复杂度：O(n^2)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums)
    {
        sort(nums.begin(), nums.end());

        vector<vector<int>> res;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > 0) {
                break;
            }
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int m = i + 1;
            int n = nums.size() - 1;
            while (m < n) {
                if (nums[m] + nums[n] == -nums[i]) {
                    res.push_back(vector<int> { nums[i], nums[m], nums[n] });
                    m++;
                    n--;
                    while (m < n && nums[m] == nums[m - 1]) {
                        m++;
                    }
                    while (n > m && nums[n] == nums[n + 1]) {
                        n--;
                    }
                } else if (nums[m] + nums[n] < -nums[i]) {
                    m++;
                    while (m < n && nums[m] == nums[m - 1]) {
                        m++;
                    }
                } else {
                    n--;
                    while (n > m && nums[n] == nums[n + 1]) {
                        n--;
                    }
                }
            }
        }

        return res;
    }
};

Contains Duplicate III

桶排序，巧妙之处在于一个捅中只会用一个元素

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        if(k <= 0 || t < 0) {
            return false;
        }
        long long tt = t;
    
        map<long long, long long> buckts;
        
        long long min_num = *max_element(nums.begin(), nums.end());
        for(int i = 0; i < nums.size(); i++) {
            if(i > k) {
                int p = i - k - 1;
                long long b = (nums[p] - min_num) / (tt + 1);
                buckts.erase(b);
            }
            
            long long b = (nums[i] - min_num) / (tt + 1);
            if(buckts.find(b - 1) != buckts.end()) {
                if(nums[i] - buckts[b - 1] <= tt) {
                   return true; 
                }
            }
            if(buckts.find(b + 1) != buckts.end()) {
                if(buckts[b + 1] - nums[i] <= tt) {
                   return true; 
                }
            }
            if(buckts.find(b) != buckts.end()) {
                return true;
            }
            buckts[b] = nums[i];
        }
        
        return false;
    }
}