[leetcode - 15. 3Sum] java

문제 설명

1. 배열이 주어진다.

2.배열에서 3개 숫자를 더해서 0이 되는 것들을 찾는다.

3. 근데 그 대상 숫자들이 중복되면 안된다.

 

풀이 과정 

1. 투포인터 문제인데, 해결 방법이 생각이 잘 안나서 많이 헤맸다.

2. 앞에서부터 뒤로 가면서 기준 인덱스의 뒤에를 투포인터로 찾으면 된다.

3. 그리고 중복되는 값들을 제거해주면서 구하면 된다.

코드

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        // 투포인터 실행을 위한 list 정렬
        Arrays.sort(nums);

        // 3개 찾아야 하니까 2개 남겨놓음
        for(int i=0; i<nums.length - 2; i++) {
            if(i != 0 && nums[i] == nums[i-1]) continue; // 숫자 중복 제거를 위함, i가 start

            int mid = i + 1; // 왼
            int end = nums.length - 1; // 오

            while(mid < end) {
                // 숫자 중복 제거
                if(mid != i+1 && nums[mid] == nums[mid-1]) {
                    mid++;
                    continue;
                } else if (end != nums.length - 1 && nums[end] == nums[end + 1]) {
                    end--;
                    continue;
                }

                // 만든 숫자가
                int num = nums[i] + nums[mid] + nums[end];
                if(num == 0) { // 정답이면 입력하고
                    ans.add(List.of(nums[i], nums[mid], nums[end]));
                    mid++; // 얘네 둘다 다시 쓰일 일 없음
                    end--;
                } else if(num < 0) { // 나머지 투포인터 진행
                    mid++;
                } else {
                    end--;
                }
            }
        }

        return ans;
    }
}