标签：right 15 nums int 三元组 四数 && left

454. 四数相加 II

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

• 0 <= i, j, k, l < n
• nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

示例 1：

输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

示例 2：

输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1

思路：

这道题目是四个独立的数组，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考虑有重复的四个元素相加等于0的情况

参考昨天做的两数之和，连想到（a+b+c+d）可以拆开看（a+b)和（c+d)。

那就可以看作是先统计（a+b)两元素之和及其出现的次数，再在统计结果中找（0-（c+d)）元素出现的次数。其中（c+d）也是需要遍历计算的。

遍历统计，就要用到for循环。

统计元素之和及其出现的次数，这里记录需要两个变量，联想要用哈希表中的map。其中key是元素之和，value是出现的次数。

map[key]=value

定义一个变量count，用来统计 a+b+c+d = 0 出现的次数。

心得：

在有两个变量需要记录的时候考虑使用map，要搞清楚value和key对应的变量。

这种找相加结果target_sum是否存在的题通常使用这种方法：在set/map中判断【target_sum-已知元素】这个元素是否出现过，即哈希表法。但是用set还是map需要具体问题具体分析。

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int,int> umap;//设立一个map结构，key是（a+b)，valude是其出现的次数
        //遍历nums1和nums2，统计a+b的和的出现的次数
        for(int a:nums1)
            for(int b:nums2)
                umap[a+b]++;
        int count=0;
        for(int c:nums3)
            for(int d:nums4)
                if(umap.find(0-(c+d))!=umap.end())
                {
                    count+=umap[0-(c+d)];
                }
                    
    return count;
    }
};

383.赎金信

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

示例 1：

输入：ransomNote = "a", magazine = "b"
输出：false

示例 2：

输入：ransomNote = "aa", magazine = "ab"
输出：false

示例 3：

输入：ransomNote = "aa", magazine = "aab"
输出：true

思路：

本题是数组在哈希法中的应用。可以参考242.有效的字母异位词

在本题的情况下，使用map的空间消耗要比数组大一些的，因为map要维护红黑树或者哈希表，而且还要做哈希函数，是费时的！数据量大的话就能体现出来差别了。 所以数组更加简单直接有效！

心得：

省题还是很重要的。

刚开始还以为是要求判断 ransomNote 能不能由 magazine 里面的字符构成还要考虑字符的连续性。

但是其实只确保要 magazine 和ransomNote 里同时出现的字符的个数中， magazine 的大于等于ransomNote 的就可以了，相反，如果小于，就肯定不能构成了。

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int record1[26]={0};
        int record2[26]={0};

        for(int i=0;i<ransomNote.size();i++)
            record1[ransomNote[i]-'a']++;
        for(int i=0;i<magazine.size();i++)
            record2[magazine[i]-'a']++;
        int cnt=0;
        for(int i=0;i<26;i++)
        {
            if(record1[i]!=0&&record1[i]>record2[i])//如果record1[i]的元素多与record2[i]，就说明 ransomNote 肯定不能由 magazine 里面的字符构成了
            {
                return false;//返回 false
            }
        }
        return true;//能走完循环，说明每个字母都通过了判断，返回 true

    }
};

15. 三数之和（双指针）

给你一个整数数组 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]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

思路：

哈希表不是一个好的选择，本题采用的是双指针法。

步骤：

1. 先对数组进行排序，由小到大
2. 题意：在数组中找到 abc 使得a + b +c =0。那就做一层for循环，i从下标0的地方开始，同时定一个下标left 定义在i+1的位置上，定义下标right 在数组结尾的位置上。

​ a = nums[i], b = nums[left], c = nums[right]

3. 接下来如何移动left 和right呢， 如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。

   如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。

   最重要的在于去重：（也是最难的）

   1. 首先对a去重

   因为数组已经经过排序了，所以当第一次遇到a=nums[i]这个元素的时候，经过遍历，已经把符合条件的三元组找全了，所以在遇到重复元素即相邻元素相等的时候，后面的数组因为是排过序的，所以往后的数组都是一样的，遍历的完的输出的三元组还是会和第一次遇到nums[i]的结果一样。

   那么判别条件是用

   nums[i]==nums[i-1] ？

   nums[i]==nums[i+1]？

   nums[i+1]会和nums[left]冲突，返回的结果里会漏掉一部分情况。例如【-1,-1,2】

   所以使用nums[i]==nums[i-1]。

   2. 对b c去重

   这里的去重是针对三元组，而不是针对三元组内的元素。所以对b c 去重应该在找到一个三元组之后。

   发现重复情况就指针收缩：左指针发生重复就收左边，右指针发生重复就收右边。

   别忘了去完重之后，左右指针还要再向内同时收一次才能彻底摆脱重复的三元组。

心得：

难点在于先想到双指针法，然后去重。

尤其是对于a的去重，要想明白。b c去重操作的位置也很重要。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
    //定义一个二维数组
    vector<vector<int>> result;
    //先对nums排序
    sort(nums.begin(),nums.end());
    int left,right;

    // a = nums[i], b = nums[left], c = nums[right]
    for(int i=0;i<nums.size();i++)
    {
         // 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
        if(nums[i]>0) return result;
        
        // 错误去重a方法，将会漏掉-1,-1,2 这种情况
        /*
        if (nums[i] == nums[i + 1]) {
            continue;
        }
        */
		//正确的去重操作：
        //去重操作:针对a
        if(i>0&&nums[i]==nums[i-1])//如果前后相同：出现重复
            continue;//跳过
        
        left=i+1;right=nums.size()-1;
        while(right>left)
        {
                // 去重复逻辑如果放在这里，0，0，0 的情况，可能直接导致 right<=left 了，从而漏掉了 0,0,0 这种三元组
                /*
                while (right > left && nums[right] == nums[right - 1]) right--;
                while (right > left && nums[left] == nums[left + 1]) left++;
                */
            if(nums[i]+nums[left]+nums[right]>0)
                right--;
            else if(nums[i]+nums[left]+nums[right]<0)
                left++;
            else
            {
                //找到了三元组,写入结果result
                result.push_back(vector<int>{nums[i],nums[left],nums[right]});
                //去重逻辑应该放在找到一个三元组之后，对b 和 c去重
                //去重操作:针对b,c
                while(right>left&&nums[right]==nums[right-1]) right--;
                while(right>left&&nums[left]==nums[left+1]) left++;
                // 找到答案时，双指针同时收缩
                right--;
                left++;
            }

        }
    }
    return result;
    }
};

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：

输入：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]]

思路：

和三数之和差不多。都是用双指针法。

不同的是四数之和需要两重循环for先把nums[i]+nums[k]作为确定值，再在循环内用left和right作为双指针找到

nums[k] + nums[i] + nums[left] + nums[right] == target的情况。

三数之和的时间复杂度是O(n^{2)，四数之和的时间复杂度是O(n}3) 。

由此类推，五数之和、六数之和等等都采用这种解法。

重点：

注意剪枝用break而不是返回return result。

遇到重复元素，用continue跳出。

易错点：

1. 三数之和的target固定给的是0，但是此题的target是自定义的，不能用nums[i]>target来剪枝了，除非是正值。所以要减枝要加上附加条件nums[i]>=0。

nums[i]>target&&nums[i]>=0

2. 提交时候遇到一个错误案例，所以需要加防溢出条件。把int类型强行转换成long类型。

心得：

这种题太经典了，需要定期翻出来。

尤其是双指针的应用，感觉非常灵活，没有固定的应用套路。需要多多感悟。

程序：

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
    sort(nums.begin(),nums.end());
    //定义一个二维数组
    vector<vector<int>> result;
    int left,right;
    for(int i=0;i<nums.size();i++)
    {
        if(nums[i]>target&&nums[i]>=0) {break;}//一级剪枝，注意这里用break，不能用return result;
        if(i>0&&nums[i]==nums[i-1]){continue;}//对nums[i]去重

        for(int k=i+1;k<nums.size();k++)
        {
            left=k+1;right=nums.size()-1;

            if(k>i+1&&nums[k]==nums[k-1]) {continue;}//对nums[k]去重          
            if(nums[i]+nums[k]>target&&nums[i]+nums[k]>=0) {break;}//二级剪枝

            while(right>left)
            {

                if((long)nums[i]+nums[k]+nums[left]+nums[right]>target){ right--;}
                else if((long)nums[i]+nums[k]+nums[left]+nums[right]<target) {left++;}
                else
                {
                    result.push_back(vector<int>{nums[i],nums[k],nums[left],nums[right]});
                    while(right>left&&nums[right]==nums[right-1]) right--;
                    while(right>left&&nums[left]==nums[left+1]) left++;
                    right--;
                    left++;
                }
            }

        }

    }
    return result;

    }
};

标签：right,15,nums,int,三元组,四数,&&,left
From： https://www.cnblogs.com/MLcaigou/p/16819476.html