午夜香蕉少妇A片视频,中国少妇热妇XXXXXXXXX,懂色av蜜臀av粉嫩av分享,动漫美女被吸乳羞羞,国产免费一级一级,偷偷解开女同桌的内裤摸网站,国内自拍偷拍第一页,AV毛片基地

算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問題叫做四數(shù)之和?，我們先來看題面：

https://leetcode-cn.com/problems/4sum/

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

題意

給定一個包含 n 個整數(shù)的數(shù)組 nums 和一個目標(biāo)值 target，判斷 nums 中是否存在四個元素 a，b，c 和 d ，使得 a + b + c + d 的值與 target 相等？找出所有滿足條件且不重復(fù)的四元組。

注意：答案中不可以包含重復(fù)的四元組。

樣例

給定數(shù)組 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

滿足要求的四元組集合為：
[
??[-1, 0, 0, 1],
??[-2, -1, 1, 2],
??[-2, 0, 0, 2]
]

題解

四數(shù)之和與前面三數(shù)之和的思路幾乎是一樣的。在前面的基礎(chǔ)上多添加一個遍歷的指針。

使用四個指針(a

保存使得nums[a]+nums[b]+nums[c]+nums[d]==target的解。偏大時d左移，偏小時c右移。c和d相遇時，表示以當(dāng)前的a和b為最小值的解已經(jīng)全部求得。b++,進(jìn)入下一輪循環(huán)b循環(huán)，當(dāng)b循環(huán)結(jié)束后。

a++，進(jìn)入下一輪a循環(huán)。即(a在最外層循環(huán)，里面嵌套b循環(huán)，再嵌套雙指針c,d包夾求解)。

class?Solution{
??public:
??vector<vector<int>> fourSum(vector<int>& nums, int?target) {
????????sort(nums.begin(),nums.end());
????????vector<vector<int> > res;
????????if(nums.size()<4)
????????return?res;
????????int?a,b,c,d,_size=nums.size();
????????for(a=0;a<=_size-4;a++){
??????????if(a>0&&nums[a]==nums[a-1]) continue; //確保nums[a] 改變了
??????????for(b=a+1;b<=_size-3;b++){
????????????if(b>a+1&&nums[b]==nums[b-1])continue; //確保nums[b] 改變了
????????????c=b+1,d=_size-1;
????????????while(c??????????????if(nums[a]+nums[b]+nums[c]+nums[d]??????????????????c++;
??????????????else?if(nums[a]+nums[b]+nums[c]+nums[d]>target)
??????????????????d--;
??????????????else{
????????????????res.push_back({nums[a],nums[b],nums[c],nums[d]});
????????????????while(c1]==nums[c]) //確保nums[c] 改變了
????????????????????c++;
????????????????while(c-1]==nums[d]) //確保nums[d] 改變了
????????????????????d--;
????????????????c++;
????????????????d--;
??????????}
????????}
??????}
????}
????return?res;
????}
};

作者：misakasagiri-2
鏈接：https://leetcode-cn.com/problems/4sum/solution/shuang-zhi-zhen-jie-fa-can-zhao-san-shu-zhi-he-ge-/