Blog Details

Find the sum of the two elements of a given array which is equal to an given integer

1. Description

Asked by Google.

Given a list of numbers and a number k, return whether any two numbers from the list add up to k.

2. Example

Given [10, 15, 3, 7] and k of 17, return true, since 10+7 is 17.

3. Solution – 3 ways to solve it.

package com.leet.sum;

import java.util.Arrays;
import java.util.HashMap;

public class Solution {
	// Brute Force: O(n^2), space: O(1)
	public boolean findTarget(int[] nums, int target) {
		for(int i = 0; i < nums.length; i ++) {
			for(int j = i; j < nums.length; j ++) {
				if(nums[i] + nums[j] == target) {
					return true;
				}
			}
		}
		return false;
	}
	
	// Sort it up 
	// Time space: O(nlogn), Space: O(n)
	public boolean findTarget2(int[] nums, int target) {
		Arrays.sort(nums);
		int length = nums.length;
		for(int i = length - 1; i >= 0; i --) {
			for(int j = 0; j < length - 1; j ++) {
				if((nums[i] + nums[j]) > target) {
					break;
				}
				if (nums[i] + nums[j] == target) {
					return true;
				}
			}
		}
		return false;
	}
	
	// Use HashMap: O(n) space: O(n) 
	public boolean findTarget3(int[] nums, int target) {
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		for (int i = 0; i < nums.length; i++) {
			map.put(nums[i], nums[i]);
		}
		
		for (int i : nums) {
			if(map.containsKey(target - i)) {
				return true;
			}
		}
		return false;
	}
}