1. Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

 

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

 

Constraints:

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

 

---

 

my solution

//my solution

class Solution {
    
    public int[] twoSum(int[] nums, int target) {
        
        int a=0;
        int b=0;
        
        
        for(int i=0; i<nums.length; i++){	//nums 배열을 순회
            
            int gap = target - nums[i];	//target과 배열 요소와의 차 계산=gap
        
            for(int k=0; k<nums.length; k++){	//nums 배열을 순회
            
                if(nums[k]==gap && k != i){	//gap의 값이 같으며 인덱스가 다른 요소를 탐색
                    // System.out.println(i);
                    // System.out.println(k);
                    a=i;	//발견하면 i를 변수a에 할당
                    b=k;	//k를 변수b에 할당
                    break;	//반복문 탈출
                 }
            }
        }
        

        int[] intArr = {a, b};	//각각 인덱스i와 k가 들어 있는 a와 b를 배열로 생성
        // System.out.println("intArr[0]=" + intArr[0] + " intArr[1]=" + intArr[1]);
        
        return intArr;	//반환
    }
}

해결에 오랜 시간이 필요했다. 답지를 보지 않고 해결했다는 데 의의를 둔다.

 

---

 

LeetCode solution

 

1. Brute-force

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) { //애초에 1을 더해줌으로써 i!=k 조건을 없앰
                if (nums[j] == target - nums[i]) {
                //gap변수 생성x, 
                    return new int[] { i, j };
                }
            }
        }
        // In case there is no solution, we'll just return null
        return null;
    }
}

 

2. Two-pass hash Table

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement) && map.get(complement) != i) {
                return new int[] { i, map.get(complement) };
            }
        }
        // In case there is no solution, we'll just return null
        return null;
    }
}

 

3. One-pass hash table

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i]; //target - 배열의 요소 = complement
            if (map.containsKey(complement)) { // key 존재여부확인. 있으면 true, 없으면 false 반환
                
                return new int[] { map.get(complement), i };
                //map.get(key): key에 대응하는 value를 반환
                //여기서는 value가 인덱스이므로 [index, index]를 반환한다.
            }
            map.put(nums[i], i); //맵에 key, value조합을 삽입
            //** nums[i]가 key, 인덱스가 value **
        }
        // In case there is no solution, we'll just return null
        return null;
    }
}

 

 

---

 

 

어떤 사람은 HashTable을 사용했다. 속도가 빨랐다고 한다.

HashTable에 대한 설명

https://mangkyu.tistory.com/102

class Solution {
    public int[] twoSum(int[] nums, int target) {
      Hashtable<Integer, Integer> hashTable = new Hashtable<Integer, Integer>();
      int i = 0;
      while ((i < nums.length) && (hashTable.get(nums[i]) == null)) {      
        hashTable.put(target - nums[i], i);
        i++;
      }
      if (i < nums.length) {
        return new int[]{hashTable.get(nums[i]),i};
      } 
      return null;       
    }
}