Open knasim opened 6 years ago
This assumes that the array is sorted which is not the case. Therefore this adds an overhead of O(nlogn) to sort which is slower than O(n)
right but the hashmap increases use of space. shouldn't we consider the net effect ?
@knasim Even if we go best sorting algorithm(merge/quick/tree), It will have time complexity O(nlogn) with worst space complexity O(n).
Using hashmap, we solve this in O(n) time with space O(n) even if all the elements are distinct in the array.
@IAmPramod , I reckon hashmap is implemented using Red-Black trees, so the average lookup time for a huge N becomes log N. So for N elements it again comes to O(N log N)
@sragha45 Yes, you are correct. But O(NlogN) is the worst case scenario when we have a very poor implementation of hash code which will map all entries to same bucket.
Have a look at the performance of hashmap in average case. https://dzone.com/articles/hashmap-performance
May be this is not completely related to the discussion. But with hash map and tuple together, we can solve this problem easily.
def get_count_map(nums):
count_map = dict()
for i in range(0, len(nums)):
if nums[i] in count_map:
temp = count_map[nums[i]]
temp[1].append(i)
temp = (temp[0]+1, temp[1])
count_map[nums[i]] = temp
else:
count_map[nums[i]] = (1, [i])
return count_map
def print_indices(count_map, k):
for i in count_map:
if 2*i == k:
return [count_map[i][1][0], count_map[i][1][1]]
break
else:
if k-i in count_map:
return [count_map[i][1][0], count_map[k-i][1][0]]
break
https://github.com/vin0010/Competitve-Programming/blob/master/python/leetcode/TwoSum.py
Sorting the numbers will change the indices of numbers which we need to return. If we keep record of the indices it will be a O(n) space complexity and O(n log n) time which is not good.
Here's a constant space implementation of two sum. Time Complexity is O(n^2) but the solution is much better than brute force. The answer even beats 97% in leetcode (in time) `
public int[] twoSum(int[] nums, int target) {
int high = 0, low = Integer.MAX_VALUE;
int numsSize = nums.length;
for (int a0 = 0; a0 < numsSize; a0++) {
if (nums[a0] < low)
low = nums[a0];
else if (nums[a0] > high)
high = nums[a0];
}
for (int a0 = 0; a0 < numsSize ; a0++) {
if (nums[a0] + low > target)
continue;
if (nums[a0] + high < target)
continue;
int target2 = target - nums[a0];
for (int a1 = a0 + 1; a1 < numsSize; a1++) {
if (nums[a1] == target2) {
return new int[]{a0, a1};
}
}
}
return new int[0];
}
`
邮件已收到,我会尽快回复。
来信收到,谢谢,祝您一切顺利!
您好,您的邮件我已收到!祝工作顺利,天天开心。。。
这是来自QQ邮箱的假期自动回复邮件。你好,我最近正在休假中,无法亲自回复你的邮件。我将在假期结束后,尽快给你回复。
There is a better solution for the TwoSum problem than the hashmap solution. Sure hashmap is fine and meets the desired output. however it can be completely eliminated as such. The techinque employs a pointers to track the argument array i.e. one from the begining aka
head
and the other one from the end akatail
. A single sweep on the array and adjusting the two pointers does the job rather nicely.