day7 四数相加赎金信三数之和四数之和-Toy模板网

这篇具有很好参考价值的文章主要介绍了day7 四数相加赎金信三数之和四数之和。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

- 四数相加
- 不用去重，所以简单遍历就是
- 四个数，如果四重循环，就是O n^4，反正求和相加有几组数而已，俩俩一组先加起来，前俩个用map记下来，key是加和，value是出现组次数，再遍历第三、四个数组，找加和为0的，int ret = 0，去加上记录次数就好了

- 赎金信
- int一个26长的数组，判断即可
- 和242.有效的字母异位词极其类似

- 三数之和
   - 遍历+双指针
       - 今天第一次学的，纯照葫芦画瓢
       - 先sort从小到大排好
   - 第一个数从0->nums.size()，i++遍历
       - 剪枝：因为已经排序了，所以刚开始就>0，后面再怎么加也不可能== 0，直接break就好
       - 去重：当i与i - 1所指向的数字相等，则本轮continue
   - 然后双指针，left和right，分别指向i+1，nums.size()-1，while(left < right) 一个个找就好
       - 下标i，left，right分别指向的数相加，if > 0，说明加多了，right--，反之left++
       - == 0，push_back进去记录结果的vector
       - 去重
           - left去重，while left == left+1时，说明重复元素，left++
           - right，== right-1时，right--
```cpp
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > 0) break;
            if (i && nums[i] == nums[i - 1]) continue;
            int left = i + 1, right = nums.size() - 1;
            while (left < right) {
                if (nums[i] + nums[left] + nums[right] > 0) right--;
                else if (nums[i] + nums[left] + nums[right] < 0) left++;
                else {
                    result.push_back(vector<int> {nums[i], nums[left], nums[right]});
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    left++;
                    right--;
                }
            }
        }
        return result;
    }
};
```

- 四数之和
   - 与三树之和类似，多的一个数再套一层循环就好
   - 第一、二个数剪枝
       - 因为本题求== target，不是== 0，target可能为负数，不能只是判断 > target，比如，-3，-2，-1，0，求taget=-6，很明显这组数我们是要的，但是像上面写的一样-3>-6就break了，所以加一个限定条件，target >= 0
```cpp
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++) {
if (nums[i] > target && target >= 0) break;
if (i && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < nums.size(); j++) {
if (nums[i] + nums[j] > target && target >= 0) break;
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
int left = j + 1, right = nums.size() - 1;
while (left < right) {
if ((long)nums[i] + nums[j] + nums[left] + nums[right] > target) right--;
else if ((long)nums[i] + nums[j] + nums[left] + nums[right] < target) left++;
else {
result.push_back(vector<int> {nums[i], nums[j], nums[left], nums[right]});
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
}
}
}
}
return result;
}
};
```
文章来源地址https://www.toymoban.com/news/detail-630267.html