[LeetCode-자바] N_15 3Sum

📜 문제

배열 내의 3개의 원소를 더한 값이 0이 되는 모든 경우의 수 찾기
-> 중복 경우의 수는 제외~

생각하기

배열을 정렬하고, 양수와 음수를 나눠서 풀어야 한다고 생각했다.
그래서 이진탐색으로 양수와 음수 경계의 인덱스를 먼저 찾고,
List<Integer> plus List<Integer> minus에 양수, 음수 원소들을 저장했다.

합이 0이 되는 경우

• 양수 2개+음수 1개 = 0
• 음수 2개 + 양수 1개 = 0
• 양수 1개 + 음수 1개 + 0 = 0 (배열에 0이 존재 하는 경우,)

같이 3가지 경우 중 하나라도 만족하면 답이 된다.

막상 나누고 보니, 위 세 조건을 구현하는 게 막막했다.
30분 동안 씨름 후 답을 봤다.

결론부터 말하자면,

숫자 1개를 고정하고, 남은 원소들을 투 포인터를 사용해 접근하는 방식이었다.

---

🍳 전체 소스 코드

class Solution {
	
   public static int findIdx(int[] nums){
        int start = 0;
        int end = nums.length-1;
        while(start<=end){
            int half = (start+end)/2;
            if(nums[half]==0){ return half;}
            else if(nums[half]<0){
                start =  half+1;
            }
            else{
                end = half-1;
            }
        }
        return start;
    }
    public List<List<Integer>> threeSum(int[] nums) {
        
       	Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        
        if(nums[0]>0 || nums[nums.length-1]<0){
            return res;
        } 

        int lastIdx = findIdx(nums);
        if(lastIdx <0) lastIdx++;
        for(int i=0;i<=lastIdx;i++){
            if(i>0 && nums[i]==nums[i-1]){
                continue;
            }
            int j = i+1;
            int k = nums.length-1;
            while(j<k){
                int total  = nums[i]+nums[j]+nums[k];
                if(total<0){
                    j++;
                }else if( total>0){
                    k--;
                }else{
                    res.add(Arrays.asList(nums[i],nums[j],nums[k]));
                    j++;
                    while(nums[j]==nums[j-1] && j<k){
                        j++;
                    }
                }
            }
        }
        return res;
    }
}

---

✍ 부분 코드 설명

1. 변수 선언

   public List<List<Integer>> threeSum(int[] nums) {
          Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        
        if(nums[0]>0 || nums[nums.length-1]<0){
            return res;
        } 

        int lastIdx = findIdx(nums);
        if(lastIdx <0) lastIdx++;
        
		...

• res: 경우의 수를 저장하는 리스트
• lastIdx: 첫 양수 인덱스 저장 변수

1. nums 배열 정렬
2. 반환할 res 변수 선언
3. 만일 배열 내에 음수 혹은 양수가 없다면 답이 존재할 수 없으므로 종료
4. findIdx 함수를 호출 하여, 첫 양수 인덱스를 구한다.

---

2. findIdx 함수

  public static int findIdx(int[] nums){
        int start = 0;
        int end = nums.length-1;
        while(start<=end){
            int half = (start+end)/2;
            if(nums[half]==0){ return half;}
            else if(nums[half]<0){
                start =  half+1;
            }
            else{
                end = half-1;
            }
        }
        return start;
    }

이진 탐색을 이용하여 양수 시작점 찾기. (0인 경우 0 인덱스 반환)

---

3. 변수 선언

	...
for(int i=0;i<=lastIdx;i++){
	if(i>0 && nums[i]==nums[i-1]){
    	continue;
	}
    int j = i+1;
    int k = nums.length-1;
    while(j<k){
    	int total  = nums[i]+nums[j]+nums[k];
        if(total<0){
        	j++;
		}
        else if(total>0){
			k--;
        }
        else{
			res.add(Arrays.asList(nums[i],nums[j],nums[k]));
            j++;
            while(nums[j]==nums[j-1] && j<k){
            	j++;
			}	// while
		}	// else
	}	// while
}	// for
	return res;
} // threeSum

• i: 고정수의 인덱스.
• j: i+1 ~ k까지
• k: 배열의 끝 ~ j까지

중복된 경우를 허용하지 않았으므로, 중복값이 있다면 진행하지 않고 다음 원소로 넘어간다.

끗!

---

✨ 결과

세 원소를 가지고 풀어야 하는 문제를 또 마주치게 된다면 이 접근법을 사용해야겠다.
넘 어려워 보였지만,, 풀고 정리까지 하니 좀 친해졌다.