---
tags: Leetcode
---
# Two Sum

## Approach 1: Brute Force

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int size = nums.length;
        
        for( int i = 0; i < size; i++ ){
            for( int j = i + 1; j < nums.length; j++ ){
                if( nums[i] + nums[j] == target ){
                    return new int[]{i,j};
                }
            }
        }
        
        throw new IllegalArgumentException("No two sum solution");
    }
}

## Approach 2: Two-pass Hash Table

class Solution {
    public int[] twoSum(int[] nums, int target) {
        
        // set a map 
        Map<Integer, Integer> map = new HashMap<>();
        
        // put into map
        for( int i = 0; i < nums.length; i++ ){
            map.put(nums[i], i);
        }
        
        // compare map
        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)};
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

## Approach 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];
            if( map.containsKey(complement)){
                return new int[] {map.get(complement), i};
            }
            map.put(nums[i], i );
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

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