双指针算法实战：有效三角形与多数之和

1、有效三角形的个数

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

示例 1: 输入: nums = [2,2,3,4] 输出: 3 解释: 有效的组合是: 2,3,4 (使用第一个 2), 2,3,4 (使用第二个 2), 2,2,3

示例 2: 输入: nums = [4,2,3,4] 输出: 4

解题思路：

1. 暴力解法：枚举所有的三条边，判断它们是否可以组成三角形，记录有效三角形的个数。不过 n^3 的时间复杂度会超出时间限制！

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int len=nums.size(),count=0;
        for(int a=0;a<len-2;a++) {
            for(int b=a+1;b<len-1;b++) {
                for(int c=b+1;c<len;c++) {
                    if(nums[a]+nums[b]>nums[c] &&nums[a]+nums[c]>nums[b] &&nums[b]+nums[c]>nums[a]) count++;
                }
            }
        }
        return count;
    }
};

2. 更优解法：先将数组排序，因为判断三个数是否可以构成三角形只需要比较较小两边之和是否大于第三边即可。

3. 排序后，nums[len-1]的位置就是最大值，我们先用 right_idx 固定一端，right 固定在 right_idx 左侧，left 固定在起点。

4. 判断 nums[left]+nums[right] 是否大于 nums[right_idx]。

   • a. 如果小于，left++
   • b. 如果大于，count+=(right-left)。固定 right_idx 和 right 两边后，left 是 right 之后最小的一边。如果最小的一边加上 right 都大于 right_idx，那其后的边一定可以构成三角形。所以我们就没有必要进行无意义的枚举。
   • c. 此时固定 right_idx 和 right 的情况已近枚举完成，那我们就让 right--。

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int right_idx=nums.size()-1,count=0;
        //排序
        sort(nums.begin(),nums.end());
        //固定枚举 right_idx
        while(right_idx>=2) {
            //固定枚举 right
            int right=right_idx-1;
            int left=0;
            while(left<right) {
                if(nums[left]+nums[right]>nums[right_idx]) {
                    count+=(right-left);
                    right--;
                } else left++;
            }
            right_idx--;
        }
        return count;
    }
};

2、查找总价值为目标值的两个商品

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

示例 1： 输入：price = [3, 9, 12, 15], target = 18 输出：[3,15] 或者 [15,3]

示例 2： 输入：price = [8, 21, 27, 34, 52, 66], target = 61 输出：[27,34] 或者 [34,27]

class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        int left=0,right=price.size()-1;
        while(left<right) {
            if(price[left]+price[right]<target) left++;
            else if(price[left]+price[right]>target) right--;
            else {
                return {price[left],price[right]};
            }
        }
        return {-1,-1};
    }
};

3、三数之和

给你一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k，同时还满足 nums[i] + nums[j] + nums[k] == 0。请你返回所有和为 0 且不重复的三元组。

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

示例 1： 输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]]

示例 2： 输入：nums = [0,1,1] 输出：[]

示例 3： 输入：nums = [0,0,0] 输出：[[0,0,0]]

解题思路：

1. 这个题目的整体思路可以转化为两数之和==target，和上一道题目相似，不过在细节上还是有些不同。
2. 排序后，我们定义 k 在 len-1 的位置，left=0，right=k-1。判断 nums[left]+nums[right]==-nums[k] 就可以了。

去重问题：

找到一个三元组后，left++，right--。

• a. 如果 left==left-1（逻辑修正：指移动后值相同），那么我们找到的下一个三元组必然和前一个相等！(因为 left 和 k 固定了)
• b. 同理，如果 right==right+1（逻辑修正：指移动后值相同），那么我们找到的下一个三元组必然和前一个相等！
• c. 再有，如果 k==k+1（逻辑修正：指外层循环移动后值相同），我们在下一个区间查找的所有情况再上一个区间都查找过了！
• d. 所以这三种情况我们都要跳过相同的元素来进行去重操作！

解题代码：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        sort(nums.begin(),nums.end());//排序
        int len=nums.size();
        for(int k=len-1;k>=2;) {
            if(nums[k]<0) break;//小优化
            int left=0,right=k-1;
            while(left<right) {
                if(nums[left]+nums[right]<-nums[k]) left++;
                else if(nums[left]+nums[right]>-nums[k]) right--;
                else {
                    ret.push_back({nums[left++],nums[right--],nums[k]});
                    //去重
                    while(left<right&&nums[left]==nums[left-1]) left++;
                    while(left<right&&nums[right]==nums[right+1]) right--;
                }
            }
            //去重
            k--;
            while(k>=2&&nums[k]==nums[k+1]) k--;
        }
        return ret;
    }
};

4、四数之和

给你一个由 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： 输入：nums = [1,0,-1,0,-2,2], target = 0 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2： 输入：nums = [2,2,2,2,2], target = 8 输出：[[2,2,2,2]]

解题思路：

1. 这道题目的整体思路和三数之和差不多，我们可以把上一题理解为两数之和==target(0) - 一个数（自己固定枚举）。
2. 而这道题目无非就是再三数之和的基础上，再多枚举一个数而已！

解题代码：

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int len=nums.size();
        sort(nums.begin(),nums.end());
        vector<vector<int>> ret;
        for(int d=len-1;d>=3;) {
            if(target<0&&nums[0]>=0) break;//小优化
            //三数之和逻辑
            for(int c=d-1;c>=2;) {
                long long tmp=(long long)target-nums[c]-nums[d];
                int left=0;
                int right=c-1;
                while(left<right) {
                    if(nums[left]+nums[right]<tmp) left++;
                    else if(nums[left]+nums[right]>tmp) right--;
                    else {
                        ret.push_back({nums[left++],nums[right--],nums[c],nums[d]});
                        //left,right去重
                        while(left<right&&nums[left]==nums[left-1]) left++;
                        while(left<right&&nums[right]==nums[right+1]) right--;
                    }
                }
                //c去重
                c--;
                while(c>=2&&nums[c]==nums[c+1]) c--;
            }
            //d去重
            d--;
            while(d>=3&&nums[d]==nums[d+1]) d--;
        }
        return ret;
    }
};