leetcode-15-3sum

1つの配列を与えて、その中のすべての3つの数を合わせて0に等しい組み合わせを選びます.python:

class Solution(object):
    def threeSum(self, nums):
        """ :type nums: List[int] :rtype: List[List[int]] """
        nums.sort()
        m=len(nums)
        a=[]
        for i in range(m-2):
            j=i+1
            k=m-1
            while(j<k):
                if nums[j]+nums[k]>-nums[i]:
                    k-=1
                elif nums[j]+nums[k]<-nums[i]:
                    j+=1
                else:
                    if [nums[i],nums[j],nums[k]] not in a:
                        a.append([nums[i],nums[j],nums[k]])
                    j+=1
                    k-=1
                    while j < k and nums[j] == nums[j - 1]:  
                        j += 1  
                    while j < k and nums[k] == nums[k + 1]:  
                        k -= 1  //        
        return a

構想:まず順番に並べて、それからmost waterの問題と似たようなジェイ天佑がトンネルを掘ったに違いない.ijkの3つの数、iに対して遍歴します.jはiの次を指し,kは最後を指す.両側を中央に遍歴する.また、非繰返し機構appendと非繰返し計算iと同じ次のi+1を確保するプロセスもある.複雑度o(n*n).1回のループに2 sumを加える方法.判断は1サイクルに代わる.
c++:

class Solution {  
public:  
    vector<vector<int> > threeSum(vector<int> &num) {  
        // Start typing your C/C++ solution below 
        // DO NOT write int main() function 

        vector<vector<int> > ret;  
         ret.clear();  
        sort(num.begin(),num.end());  
        for(int i=0; i!=num.size();i++){  
            if(i > 0 && num[i]==num[i-1])  
                continue;  
            int j,k;  
            j=i+1;  
            k=num.size()-1;  
            while(j<k){  
                if(j>i+1&&num[j]==num[j-1]){   
                    j++;  
                    continue;  
                }  
                if(k<num.size()-1&& num[k]==num[k+1]){  
                    k--;  
                    continue;  
                }  
                 int sum = num[i] + num[j] + num[k];  
                if(sum>0){  
                    k--;  
                }else if(sum<0){  
                    j++;  
                }else{  
                    vector<int> tmp;  
                    tmp.push_back(num[i]);  
                    tmp.push_back(num[j]);  
                    tmp.push_back(num[k]);  
                    ret.push_back(tmp);  
                    j++;  
                }  
            }  
        }  
        return ret;  

    }  
};

この中にvectorの使い方があります.配列を動的に申請する必要はありません.push_backの使い方.