[LeetCode] 15. 3sum (python, javascript, two pointer)

제일 왼쪽은 고정해놓고 그 오른쪽만 투포인터로 계산한다. O(n^2)

정렬해놓고 합이 작으면 더 큰 곳으로 이동하고 크면 오른쪽 포인터를 왼쪽으로 이동시킨다

같은 원소가 있는 부분은 넘어가면서 구한다

 

1. python 

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res=[]
        for i in range(len(nums)-2):
            if i>0 and nums[i]==nums[i-1]: continue # 중복인 경우 넘어간다
                
            left,right=i+1,len(nums)-1
            while left<right:
                print(left,right)
                sum=nums[i]+nums[left]+nums[right]
                if sum<0: left+=1
                elif sum>0: right-=1
                else:
                    res.append([nums[i],nums[left],nums[right]])
                    while left<right and nums[left]==nums[left+1]:
                    #중복 불가이므로 같은 원소인 부분은 넘어간다 
                        left+=1
                    while left<right and nums[right]==nums[right-1]:
                        right-=1
                    left+=1
                    right-=1
        return res

 

2. javascript

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    const arr= [];
    nums=nums.sort((a,b)=>a-b);
    // console.log(nums)
    for(let i=0;i<nums.length-2;i++){
        let l=i+1;
        let r=nums.length-1;
        if(i>0 && nums[i]==nums[i-1])continue;
        while(l<r){
            let sum=nums[i]+nums[l]+nums[r];
            if(sum===0){
                arr.push([nums[i],nums[l],nums[r]]);
                while(l<r && nums[l]==nums[l+1]){
                    l+=1;
                }
                while(l<r && nums[r]==nums[r-1]){
                    r-=1;
                }
                l+=1;
                r-=1;
            }else if(sum<0){
                l+=1;
            }else{
                r-=1;
            }
            
        }
    }
    return arr;
    
};