'Algorithm (two-sum) time complexity comparison
Relates to this leetcode question: https://leetcode.com/problems/two-sum/
This is my solution to 2 Sum, it takes ~45ms runtime:
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] res=new int[2];
for (int i=0; i<nums.length; i++) {
for (int j=i+1; j<nums.length; j++) {
if(nums[i] + nums[j] == target) {
res[0] = i;
res[1] = j;
return res;
}
}
}
return res;
}
}
and below is the best rated 0ms solution which beats 100% Java solutions:
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] arr = new int[2];
for (int i = 1; i < nums.length; i++) {
for (int j = i; j < nums.length; j++) {
if (nums[j] + nums[j - i] == target) {
arr[0] = j - i;
arr[1] = j;
return arr;
}
}
}
return arr;
}
}
As far as I understand, both of the solutions make same number of array accesses to find the result. The only actual difference is the if-condition:
if(nums[i] + nums[j] == target) {
vs
if (nums[j] + nums[j - i] == target) {
I am really unable to get how does this make such a big difference!!
Please clarify this ambiguity to me. Thanks :)
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
