OJ刷题总结 1

来源于：https://www.bilibili.com/video/BV1bP411c7oJ/?spm_id_from=333.788&vd_source=738644d63e97553d6e3dc1cd66a642d6

相向双指针

此消彼长是双向双指针的核心。

leetcode 167（两数之和 II）

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

考虑样例
[2, 3, 4, 6, 8]，target = 9

无脑做法，2层for循环。但是没有用排序这个性质。

我们随便选择两个数字,[3, 8]，相加得11.由于数组已经排好序了，所以8和3到8之间的任意数字（3，4，6）相加，都大于9.所以不用再考虑了。
因此，我们可以设置双指针 left, right分别指向0和n - 1。
nums[left] + nums[right] == 10 > 9
那么[2, 3, 4, 6] 中的任何一个数和 8 相加，都 >= 10 > 9
可以排除8，即8不可能是答案。right —

继续，此时[2, 6]， 2 + 6 = 8 < 9。同理，用2与[3, 4, 6]中任何一个数字相加都<9。因此也可以排除掉2. left ++
再继续，此时[3, 6]，3 + 6 = 9 == 9。找到答案，返回{left + 1, right + 1}(因为题目的下标从1开始)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int left = 0, right = numbers.size() - 1;
        while(1) {
            if (numbers[left] + numbers[right] < target) {
                left ++;
            }
            else if (numbers[left] + numbers[right] > target) {
                right --;
            }
            else 
                break;
        }
        return {left + 1, right + 1};
    }
};

leetcode 15（三数之和）

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

与上题类似。相当于是找到 j 和 k，使得nums[j] + nums[k] == -nums[i]
但是注意不要重复，通过与上一个num是否相等来跳过

有两个小优化：

  1. if (nums[i] + nums[i + 1] + nums[i + 2] > 0) break;
    即如果当前的nums[i]，再加上最小的两个num都仍然 > 0，可以直接结束了
  2. if (nums[i] + nums[n - 1] + nums[n - 2] < 0) continue；
    说明当前的nums[i] 太小了，即使和最大的两个num相加都不够0，直接跳过当前num，看下一个了
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
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<vector<int>> ans;
        for (int i = 0; i < n - 2; i ++) {
            int x = nums[i];
            if (i > 0 && x == nums[i - 1]) continue;
            if (x + nums[i + 1] + nums[i + 2] > 0) break;
            if (x + nums[n - 1] + nums[n - 2] < 0) continue;
            int left = i + 1;
            int right = n - 1;
            while (left < right) {
                if (x + nums[left] + nums[right] < 0) {
                    left ++;
                }
                else if (x + nums[left] + nums[right] > 0) {
                    right --;
                }
                else {
                    ans.push_back({x, nums[left], nums[right]});
                    left ++;
                    while (left < right && nums[left] == nums[left - 1]) left ++;
                    right --;
                    while (left < right && nums[right] == nums[right + 1]) right --;
                }
            }
        }
        return ans;
    }
};

leetcode 2824

给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 target ，请你返回满足 0 <= i < j < n 且 nums[i] + nums[j] < target 的下标对 (i, j) 的数目。

还是一样，双向双指针。排序后，left和right此消彼长。

固定左端点，移动右端点

利用排序的性质，如果nums[left] + nums[right] < target，说明[left + 1, left + 2, …, right]与nums[left]相加，结果都是 < target。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int countPairs(vector<int>& nums, int target) {
        int ans = 0;
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int left = 0, right = n - 1;

        while (left < right) {
            if (nums[left] + nums[right] >= target) {
                right --;
            }
            else {
                ans += right - left;
                left ++;
            }
        }
        return ans;
    }
};

在做这题时，我就在想为什么是固定左端点，移动右端点呢？我们能不能固定右端点，移动左端点呢？每次ans += left。我感觉还是蛮有道理的。

但是仔细想想是不行的。因为题目给的是 < target。
我们的右端点是往左移动的。考虑一种情况。left和right是紧紧挨着的，也就是right == left + 1.下一回合时，right —。left为了得到满足nums[left] + nums[right]的最大值下标，left ++。而我们的大前提是while(left < right)，不对。但是这种情况下，仍然可以ans += left。

归根结底，是因为 < target。当我们固定左端点的时候，left和right两者相遇的时候，是nums[left] + nums[right] >= target的情况（因为需要right的减小来满足 < target）。而固定右端点的时候，left和right两者相遇，却是因为left ++（nums[left] + nums[right]一直 < target，可以一直增大left）。

说的有点绕，希望能看懂。。。我声明一下，这是类似于算法的笔记，写给自己看的。您要是没看懂，去看灵神的解释（嘶，忽然想起来灵神没写）。我反正尽力写了。毕竟是给自己看的hh

固定右端点，可以用二分来找左端点。虽然，固定左端点，也能用二分找右端点。

leetcode 16

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

类似，给出代码：

break和continue的优化，也类似，不赘述

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
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int diff = INT_MAX;
        int ans = 0;
        for (int i = 0; i < n - 2; i ++) {
            int x = nums[i];
            int left = i + 1, right = n - 1;
            int s = x + nums[i + 1] + nums[i + 2];
            if (s > target) {
                if (s - target < diff) {
                    ans = s;
                }
                break;
            }
            s = x + nums[n - 1] + nums[n - 2];
            if (s < target) {
                if (target - s < diff) {
                    diff = target - s;
                    ans = s;
                }
                continue;
            }
            while (left < right) {
            if (abs(target - (x + nums[left] + nums[right])) < diff) {
                ans = x + nums[left] + nums[right];
                diff = abs(target - (x + nums[left] + nums[right]));
            }
            if (x + nums[left] + nums[right] < target) {
                left ++;
            }
            else if (x + nums[left] + nums[right] > target) {
                right --;
            }
            else break;
            }

        }
        return ans;
    }
};

leetcode 18

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

  • 0 <= a, b, c, d < n
  • a、b、c 和 d 互不相同
  • nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

类似，不赘述

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
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int n = nums.size();
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n - 3; i ++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1; j < n - 2; j ++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
              
                long s = (long)nums[i] + nums[j] + nums[j + 1] + nums[j + 2];
                if (s > target) break;
                s = (long)nums[i] + nums[j] + nums[n - 1] + nums[n - 2];
                if (s < target) continue; 

                int left = j + 1, right = n - 1;

                while (left < right) {
                    long s = (long)nums[i] + nums[j] + nums[left] + nums[right];
                    if (s < target) {
                        left ++;
                    }
                    else if (s > target) {
                        right --;
                    }
                    else {
                        ans.push_back({nums[i], nums[j], nums[left], nums[right]});
                        left ++;
                        while (left < right && nums[left] == nums[left - 1]) left++;
                        right --;
                        while (left < right && nums[right] == nums[right + 1]) right --;
                    }
                }
            }
        }
        return ans;
    }
};

leetcode 611

给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

组成三角形，换句话说，也就是对三条边的任意两条边相加，其值都大于第三条边。

排序后，随机选出3个值，a < b < c。显然，a + c > b, b + c > a, 我们需要确定是否 a + b > c。这就很像leetcode 2824这题。此时，是 > target的。所以，我们是要固定右端点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());

        int ans = 0;
        int n = nums.size();
        for (int i = n - 1; i >= 2; i --) {
            int left = 0, right = i - 1;
            if (nums[i - 1] + nums[i - 2] < nums[i]) continue;
            while (left < right) {
                if (nums[left] + nums[right] <= nums[i]) {
                    left ++;
                }
                else {
                    ans += right - left;
                    right --;
                }
            } 
        }
        return ans;
    }
};