K-Sum
type
status
date
slug
summary
tags
category
icon
password
K sum problems are the sort of problems that asking you to find the k numbers whose sum is the target when given a number array or list. On LeetCode, there are two sum and three sum problems. Today, I am gonna discuss such kind of problems.
Two Sum
Easily, we can think of two simple and direct solutions. One is to try all possible combinations. Another one is to use two pointers beginning at the head and the tail of the sorted list to traverse the list in an O(n) time.
Obviously, nobody wants the first solution to happen. So let us focus on the second one.
You may write code in this way.
Unfortunately, you will find you got WA on LeetCode. The reason is this problem asks you to return the index of the numbers in the original array. So you may find another method so as to get rid of using sorting. That should be in .
Actually, in in Python is a O(n) time complexity operation. Though this code works, it may not be the best one. Other thoughts can be considering save the original list or use dict as a hash map, which can be regarded as a tradeoff between time-consuming and space-consuming to keep the time complexity as O(n2) .
Three Sum
With one more element enrolled, what we can do here is to traverse all elements, and then find the other two elements with a similar method in problem two sum.
The time complexity is O(n2) .
Actually we can still use hash map here to ensure the complexity as O(n2).
Four Sum
Similar to the problem three sum, we can fix two elements and find the other two elements with the method we use in two sum. In this way, the time complexity is O(n3) .
Are there any more optimal ways? Hashmap.
- define a hashmap whose key=a+b and value=(a, b)
- use two for to traverse all c and d.
The time complexity is O(n2logn).
Loading...