[LeetCode] Two Sum

https://leetcode.com/problems/two-sum/

초기 답안

class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        val len = nums.size

        for (i in 0 until len) {
            for (j in 0 until len) {
                if (i == j) continue
                if (nums[i] + nums[j] == target) {
                    return intArrayOf(i, j)
                }
            }
        }
        return intArrayOf()
    }
}

최종 답안

class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        val map = mutableMapOf<Int, Int>()

        for ((index, value) in nums.withIndex()) {
            val complement = target - value
            if (map.containsKey(complement)) {
                return intArrayOf(map[complement]!!, index)
            }

            map[value] = index
        }

        return intArrayOf()
    }
}

IntArray in Kotlin

intArray is specialized array type for storing primitive integers
maps directly to int[] in Java

comparison: IntArray, Array<Int> List<Int>

✅ Comparison: IntArray, Array<Int>, and List<Int>

Feature	IntArray	Array<Int>	List<Int>
Type	Primitive Array	Generic Object Array	Interface
Memory Usage	More efficient (direct storage of primitive values)	Less efficient (stores boxed integers)	Dynamic allocation
Performance	Faster (no boxing/unboxing)	Slower (boxing overhead)	Slower (dynamic resizing)
Nullability	Cannot hold null	Can hold null	Can hold null
Size	Fixed size	Fixed size	Dynamic size
Initialization	IntArray(5) / intArrayOf(1, 2)	arrayOf(1, 2)	listOf(1, 2) / mutableListOf(1, 2)
Mutability	Mutable	Mutable	Mutable/Immutable
Access Speed	Fast (direct memory access)	Slower (reference lookup)	Slower (dynamic structure)
Use Case	Performance-critical operations	Generic data structures	Dynamic collections

대부분의 차이점은 type이 다르기 때문에 발생하는 것으로 이해할 수 있다. (hold null 등)

수정도 안되는 listOf()의 존재 이유
kotlin에서는 immutable한 속성이 코드를 predictable하고, thread-safe하게 만들어준다고 생각한다. 이게 best practice임.

index로 접근하고자 하는 경우 주로 Array를 사용하고, fixed-sized인 경우에도 주로 사용
low-level data like image pixels, buffer data, arrays required by APIs

dynamic collection인 경우(크기 변경되는 경우) List 사용.
method 통해서 고차원적인 수정 하고싶을 때(filter, map, forEach)

일반적으로 List가 선호됨. 퍼포먼스가 중요한 경우에 Array 사용

usage

// creation
val arr1: IntArray = intArrayOf(1, 2, 3)
val arr2 = IntArray(5) // size
val arr3 = IntArray(5) { index -> index * 2 }

// access
println(arr1[0])

// modify
arr1[0] = 3

// get size
println(arr1.size)

에러가 발생한 이유는, primitive type인 IntArray가 필요한데 자꾸 Array를 리턴했기 때문이다. 해결책으로는 intArrayOf로 가져오거나 Array를 array.toIntArray()로 바꾸는 두 가지가 있다.

for in Kotlin

https://tourspace.tistory.com/100

Primitive Types and Boxing/Unboxing

Primitive type

stored directly in memory as raw values
memory-efficient, faster (no need to follow a memory address)
Int Double Boolean

Object type(Boxed type)

Integer in Kotlin, Int? in Java
stored as references(memory addresses) pointing to the actual value
The value itself is stored in heap memory
==: value comparison, ===: reference comparison

1) primitive type은 memory(stack)에 직접적으로 실제 값을 저장하지만 object type은 heap에 실제값이 있고 memory에 그 address 값을 저장한다.
2) 굳이 사용하는 이유
Nuallability, Collections, Generic위해서

boxing and unboxing

boxing: primitive type >> wrapper object type
unboxing: wrapper object type >> primitive type

val list = listOf(1, 2, 3) // boxing
val x: Int = list[0] // unboxing

문제 풀이

문제를 O(N^2)로 풀었는데, 사실 O(N)으로 풀어야 한다.
이중 for문을 사용하였는데 HashMap을 사용하면 IntArray를 한 바퀴만 돌면서 값을 구할 수 있다.

Your Question Translated:
"Then in this problem (Two Sum), which algorithms are used? And can you recommend any similar problems?"

---

✅ Algorithms Used in Two Sum

The main algorithmic techniques utilized in the optimal solution for the Two Sum problem include:

1. Hash Map for Lookup (Hashing)

   • The use of a hash map ensures constant-time complexity (O(1)) for lookups.
   • It maps numbers to their indices, allowing quick checks for the complement of the current number.

2. Iterative Search

   • The algorithm iterates through the array exactly once, making it linear-time (O(n)).

---

✅ Similar Problems to Try

Here are some LeetCode problems that build on similar concepts (hashing, arrays, complements):

Problem	Concept/Similarity	Difficulty
3 Sum	Extends Two Sum to find three numbers that sum to a target	Medium
4 Sum	Extends Two Sum to four numbers	Medium
Subarray Sum Equals K	Hash map with cumulative sums	Medium
Two Sum II (Input Array is Sorted)	Variation of Two Sum with sorted array and two pointers	Medium
Two Sum IV - Input is a BST	Two Sum applied to binary search trees	Easy
Longest Substring Without Repeating Characters	Hashing to track unique characters in a substring	Medium

---

🚀 Recommendation for Learning Progression

1. Start with Two Sum II, as it’s a direct variation using a sorted array and introduces the two-pointer technique.
2. Move to 3 Sum and 4 Sum for multi-dimensional extensions.
3. Try Subarray Sum Equals K for a deeper understanding of hash maps and prefix sums.

Let me know if you want a deeper explanation of any of these problems! 😊

3Sums

사용 기술과 그 근거

1) sort
duplicate 될 수 있고, 답에서 순서가 무관하다고 했음.
O(N log N)이 걸림. 단순히 함수 사용했을 때
2) two pointer tequnique
앞에서부터/뒤에서부터 훑으면 O(n)의 속도로 확인 가능 (한번씩만 값을 확인하면 되니까)
sort되어 있음

추가
1) duplicate 방지를 위해 앞/뒤 값이 동일한지 확인해서 동일한 경우 칸을 뒤로 옮긴다.

two pointer technique 사용하는 경우

• Array or List is Sorted
• Searching for a pair that meet a condition
• window or range-based problem