Question
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
Solution 1 : Brute Force
■ 1st Submission
class Solution { public int[] twoSum(int[] nums, int target) { for (int i = 0; i < nums.length; i++) { for (int j = 0; j < nums.length && j != i; j++) { // [1] if (nums[i] + nums[j] == target) { return new int[]{i, j}; } } } throw new IllegalArgumentException("No two sum solution"); }} Finished Runtime: 0 ms Your input [2,7,11,15] 9 Output [1,0] Expected [0,1]
- Oops, [1] shows that I am not fully understanding the procedure of the "for" loop
■ 2nd Submission
Brute Force with correct "for" loop
class Solution { public int[] twoSum(int[] nums, int target) { for (int i = 0; i < nums.length; i++) { for (int j = 0; j < nums.length; j++) { // [2] if (j == i) continue; if (nums[i] + nums[j] == target) return new int[]{i, j}; } } throw new IllegalArgumentException("No two sum solution"); }} Status Accepted Runtime 75 ms Memory 27.7 MB
- [2] makes a "drawback" that causes unnecessary calculation
- Time Complexity : O(n²), Space Complexity : O(1)
■ 3rd Submission
Time-optimized 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++) { if (nums[i] + nums[j] == target) return new int[]{i, j}; } } throw new IllegalArgumentException("No two sum solution"); }} Status Accepted Runtime 35 ms Memory 27.6 MB
- Is there any other better algorithm?
Solution 2 : ?
See you later