[Java] leetcode 15. 3Sum

문제

3Sum - LeetCode

3Sum - LeetCode

 

알아야 할 개념

• 투포인터

풀이

3가지의 합이 0 이되는 것을 찾는 문제.

접근법은 투포인터를 사용하여 문제 풀이 하였다. 

풀이 알고리즘은 다음과 같다. 

1. 주어진 배열을 정렬한다.
2.  3가지의 숫자를 찾아야 함으로 선형 탐색으로 숫자를 하나 뽑는다. 
3. 투포인터로 나머지 두 숫자를 탐색한다.
   1. left , right 포인터를 만든다
   2. left + right > targetVal 인 경우 작게 만들어야 하니깐 right 를 왼쪽으로 이동한다.
   3. left + right < targetVal 인 경우 크게 만들어야 하니깐 left 를 오른쪽으로 이동시킨다.
   4. left + right == targetVal 이면 정답 배열에 담는다.
   5. 중복 제거해서 3-1,2,3,4 를 구현한다.
4. 정답 배열을 리턴한다.

 

코드

자바

class Solution {
    List<List<Integer>> ans;
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        ans = new ArrayList<>();
        for(int i = 0 ;i < nums.length-2;i ++){
            if(i > 0 && nums[i] == nums[i-1])continue;
            helper(nums, i);
        }
        return ans;
    }
    public void helper(int[] nums, int targetIndex){
        int target = nums[targetIndex] * (-1);
        int left = targetIndex +1;
        int right = nums.length-1;
        int val;
        int len = nums.length;
        while(left < right){
            val = nums[left] + nums[right];
            if(val == target){
                ans.add(Arrays.asList(nums[left], nums[right], nums[targetIndex]));
                left++;
                right--;
                while(left +1 <len && nums[left] == nums[left-1])left++;
                while(right-1 > -1 && nums[right] == nums[right+1])right--;
            }else if(val > target){
                right--;
                while(right-1 > -1 && nums[right] == nums[right+1])right--;
            }else{
                left++;
                while(left +1 <len && nums[left] == nums[left-1])left++;
            }
        }
    }
}