A.P - 3sum(LeetCode, medium)

미해결

1. 문제

• 숫자로 이루어진 배열이 주어짐
• 그 안의 숫자 3개를 더해서 0이 되는 조합을 배열로 만들어 이중 배열로 리턴

2. 수도코드

	// 0이 되는 조건을 먼저 고민
    // 셋다 0일때, 2개의 합의 음수값이 3번째와 같을 때

    // 0이 3개가 있는지 체크, 있다면 결과 배열에 담고
    // 두개 이상 같은 값이 있을 경우, 그 두수의 합의 음수값과 일치하는 것이 있는지 확인, 있다면 결과 배열에 담고
    // 중복 값들을 제거
    // 1번을 pick, 2번을 pick
    // 나머지 중 1번과 2번의 합의 음수값과 일치하는 값이 있는지 찾고
    // 있다면, 3 수를 한 배열에 담아서 결과 배열에 저장
    // 없다면, 2번을 다음 수로 pick하고 남은 수들과 또 비교
    // 끝까지 돌고나면, 1번을 바꾸고 다시 진행
    // 1번이 마지막 세개일때까지 확인하고 종료
    // 결과 배열을 리턴

3. 시도

var threeSum = function(nums) {
    // 결과 배열
    let result = [];

    // 예외 사항
    // 0이 3개 이상 포함된 경우, 결과에 저장
    if (nums.filter(e => e === 0).length >= 3) {
        result.push([0,0,0])
        }
    // 같은 수가 2개 있는 경우, -n*2의 값이 있는지 체크하고 저장
    const dupl = [...new Set(nums.filter((i, x) => nums.indexOf(i) !== x))]
    dupl.map((e) => {
        let pick = nums.filter(n => n === -e*2 && n !== 0)
        if (pick.length) result.push([e,e,pick[0]])
    })

    // 위를 제외하고 나면 전체 배열의 중복값을 제거한 후 계산 가능
    let setArr = [...new Set(nums)];

    // 중복 제거한 값이 3개가 안되면 종료
    if (setArr.length < 3) return result;

    // 현재 위치, 앞의 값은 무시됨
    let cur = 0;
    while (cur < setArr.length - 2) {
        let next = cur + 1
         while (next < setArr.length - 1) {
            for (let i = next + 1; i <= setArr.length - 1; i++) {
                if (setArr[cur] + setArr[next] + setArr[i] === 0) {
                    let pick = [setArr[cur], setArr[next], setArr[i]].sort((a, b) => a - b)
                    let check = true
                    // pick이 result에 있는 값인지 검사하는 로직
                    for (let i = 0; i < result.length; i++) {
                        check = check && !(JSON.stringify(result[i]) === JSON.stringify(pick))
                    }
                    if (check) {
                        result.push(pick)
                        break;
                    } else break;
                }
            }
            next++;
        }
        cur++;
    }
    return result;
};

• 시간 초과, 이중 while에 반복문까지 겹쳐서 초과되는 것으로 판단
• 2번 while문에서 계산할 배열을 중복값을 제거하고 시도, 마찬가지로 실패
• 시간복잡도에 대한 고려가 부족함

4. 레퍼런스

• map을 활용하여 중복 조건 제거,