优选算法——双指针补充

五、leetcode611.有效三角形的个数

题目分析：

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

算法原理：

应用三角形任意量两边之和大于第三边；

解决方案：利用单调性解决；

​ 1.先固定最大的数；

​ 2.在最大的数的左边区间，使用双指针算法，快速统计出符合要求的三元组个数；

代码实现：

int triangleNumber(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    int sum = 0;
    for (int i = nums.size() - 1; i >= 2; i--) {
        int left = 0;
        int right = i - 1;
        while (left < right) {
            if (nums[left] + nums[right] > nums[i]) {
                sum += right - left;
                right--;
            } else {
                left++;
            }
        }
    }
    return sum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

六、剑指offer57.和为s的两个数字

题目分析：

购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况，返回任一结果即可。

算法原理：

​ 解决方法：利用单调性使用双指针解决问题；

代码实现：

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

七、leetcode15.三数之和

题目分析：

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

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

算法原理：

​ 解法一：排序+暴力枚举+set去重；

​ 解法二：排序+双指针；

​ 1.排序；

​ 2.固定一个数a；

​ 3.剩余的数中使用双指针使得两个数之和等于-a；

​ 4.指针移动的过程中要跳过重复元素，包括遍历所有固定的数的过程当中；

​ 5.找到一种结果之后不要停下，继续向后遍历；

​ 6.还需要避免越界访问；

代码实现：

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end()); // 降序排序
    vector<vector<int>> vv;
    for (int i = 0; i < nums.size();) {
        if (nums[i] > 0) {
            break;
        }
        int left = i + 1;
        int right = nums.size() - 1;
        int target = -nums[i];
        while (left < right) {
            if (nums[left] + nums[right] < target) {
                left++;
            } else if (nums[left] + nums[right] > target) {
                right--;
            } else {
                vv.push_back({nums[i], nums[left], nums[right]});
                left++;
                right--;
                while (left < right && nums[left - 1] == nums[left]) {
                    left++;
                }
                while (left < right && nums[right + 1] == nums[right]) {
                    right--;
                }
            }
        }
        i++;
        while (i<nums.size()&&nums[i-1] == nums[i]) {
            i++;
        }
    }
    return vv;
}
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

八、leetcode18.四数之和

题目分析：

给你一个由 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

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

算法原理：

​ 解法：排序+双指针；双for循环解决；

代码实现：

vector<vector<int>> fourSum(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> vv;
    for (int i = 0; i < nums.size();) {
        for (int j = i + 1; j < nums.size();) {
            int left = j + 1;
            int right = nums.size() - 1;
            while(left<right){
                long long tmp=(long long)target-( nums[j] + nums[i]);
                long long sum=nums[left]+nums[right];
                if (sum < tmp) {
                    left++;
                } else if (sum > tmp) {
                    right--;
                } else {
                    vv.push_back({nums[left], nums[right], nums[j], nums[i]});
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left - 1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right + 1]) {
                        right--;
                    }
                }}
            j++;
            while (j < nums.size() && nums[j] == nums[j - 1]) {
                j++;
            }
        }
        i++;
        while (i < nums.size() && nums[i] == nums[i - 1]) {
            i++;
        }
    }
    return vv;
}
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