[LeetCode] 15. 세수의 합

🔗 문제

https://leetcode.com/problems/3sum/

3Sum - LeetCode

 

📝 풀이

• 순서대로 정렬하면 풀이가 더 간단해진다.
• 중복저장되는 것을 방지하기 위해 아래 코드 추가

 

💻 코드 (java)

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> answerList = new ArrayList<>();
        
        Arrays.sort(nums);
        
        
        for (int i = 0; i < (nums.length - 2); i++) {
            
            int left = (i + 1);
            int right = nums.length -1;
            
            // 답에 중복 저장 방지
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];

                if (sum < 0) {
                    left += 1;
                } else if (sum > 0) {
                    right -= 1;
                } else {
                    ArrayList<Integer> list = new ArrayList<>();
                    list.add((nums[i]));
                    list.add((nums[left]));
                    list.add((nums[right]));

                    answerList.add(list);

                    //동일한 경우의 수를 방지하기 위해 수행 (초기에 정렬했기 때문에 가능한 부분이다)
                    while (left < right && nums[left] == nums[left + 1]) {
                        left += 1;
                    }

                    while (left < right && nums[right] == nums[right - 1]) {
                        right -= 1;
                    }
                    left++;
                    right--;
                } 
            } // while
        } // for
        return answerList;
    }
}