package leetcode_study

fun threeSumUseCombination(nums: IntArray): List<List<Int>> {

// 결과를 담을 Set 자료구조

val processResult = mutableSetOf<List<Int>>()

// 주어진 배열의 크기를 담는 변수

val maxNumber = nums.size

// 조합 배열의 크기

val givenSize = 3

// 나타낼 인덱스를 구하는 배열 초기화

val indices = IntArray(givenSize)

for (i in 0 until givenSize) {

indices[i] = i

}

while (indices[givenSize - 1] < maxNumber) {

processResult.add(indices.map { nums[it] }.sorted())

var i = givenSize - 1

while (i >= 0 && indices[i] == i + maxNumber - givenSize) {

i--

}

if (i >= 0) {

indices[i]++

for (j in i + 1 until givenSize) {

indices[j] = indices[j-1] + 1

}

} else break

}

return processResult.filter { it.sum() == 0 }

}

fun threeSum(nums: IntArray): List<List<Int>> {

val processResult = mutableListOf<List<Int>>()

val sortedNums = nums.sorted()

for (i in sortedNums.indices) {

if (i > 0 && sortedNums[i] == sortedNums[i-1]) continue

var startIndex = i + 1

var lastIndex = sortedNums.size - 1

while (startIndex < lastIndex) {

val sum = sortedNums[i] + sortedNums[startIndex] + sortedNums[lastIndex]

when {

sum == 0 -> {

processResult.add(listOf(sortedNums[i], sortedNums[startIndex], sortedNums[lastIndex]))

while (startIndex < lastIndex && sortedNums[startIndex] == sortedNums[startIndex + 1]) startIndex++

while (startIndex < lastIndex && sortedNums[lastIndex] == sortedNums[lastIndex - 1]) lastIndex--

startIndex++

lastIndex--

}

sum < 0 -> {

startIndex++

}

else -> {

lastIndex--

}

}

}

}

return processResult

}