## Monday, December 14, 2015

### LeetCode 113 - Two Sum

LeetCode – Two Sum (Java)
Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

Hashsmap:
```    public int[] twoSum(int[] numbers, int target) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
int[] result = new int[2];

for (int i = 0; i < numbers.length; i++) {
if (map.containsKey(numbers[i])) {
int index = map.get(numbers[i]);
result[0] = index+1 ;
result[1] = i+1;
break;
} else {
map.put(target - numbers[i], i);
}
}

return result;
}```
https://leetcode.com/discuss/19298/very-short-and-simple-java-code-for-two-sum
public int[] twoSum(int[] numbers, int target) {

HashMap<Integer,Integer> hash = new HashMap<Integer,Integer>();
for(int i = 0; i < numbers.length; i++){

Integer diff = (Integer)(target - numbers[i]);
if(hash.containsKey(diff)){
int toReturn[] = {hash.get(diff)+1, i+1};
}

hash.put(numbers[i], i);

}
return null;
}
https://leetcode.com/discuss/48602/11-lines-and-1-for-in-java
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; i++){
if(map.containsKey(target - nums[i]))
return new int[] {map.get(target - nums[i]) + 1, i + 1};
else map.put(nums[i], i);
}
return null;
}

http://www.sigmainfy.com/blog/two-sum-problem-analysis-1-sort-hash-unique-solution.html

(1) A[left] + A[right] = target：直接返回(left+1, right+1)。
(2) A[left] + A[right] > target：说明A[right]不可能是解，right--
(3) A[left] + A[right] < target：说明A[left]不可能是解，left++

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34``` ```class Solution { class elem { public: int val; int index; elem(int v, int i):val(v),index(i) {} bool operator<(const elem &e) const { return val twoSum(vector &numbers, int target) { vector res(2,-1); vector arr; for(int i=0; i
http://blog.csdn.net/likecool21/article/details/10504885
http://www.zhangxiaolong.org/archives/844.html
https://leetcode.com/discuss/101950/java-o-nlogn-beats-98-85%25
``` public int[] twoSum(int[] numbers, int target) {
//Copy the original array and sort it
int N = numbers.length;
int[] sorted = new int[N];
System.arraycopy(numbers, 0, sorted, 0, N);
Arrays.sort(sorted);
//find the two numbers using the sorted arrays
int first = 0;
int second = sorted.length - 1;
while(first < second){
if(sorted[first] + sorted[second] < target){
first++;
continue;
}
else if(sorted[first] + sorted[second] > target){
second--;
continue;
}
else break;
}
int number1 = sorted[first];
int number2 = sorted[second];
//Find the two indexes in the original array
int index1 = -1, index2 = -1;
for(int i = 0; i < N; i++){
if((numbers[i] == number1) || (numbers[i] == number2)){
if(index1 == -1)
index1 = i + 1;
else
index2 = i + 1;
}

}
int [] result = new int[]{index1, index2};
Arrays.sort(result);
return result;
}```
https://leetcode.com/discuss/71985/my-12ms-o-nlogn-c-solution
https://leetcode.com/discuss/48383/two-c-implementations-o-n-16ms-o-nlogn-12ms
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> numsCopy(nums.begin(), nums.end());
sort(numsCopy.begin(), numsCopy.end()); // O(nlogn)

int i = 0;
int j = numsCopy.size()-1;

while (i < j)
{
int sum = numsCopy[i] + numsCopy[j];
if (sum < target)
i++;
else if (sum > target)
j--;
else
{
break;
}
}

}
{
vector<int> result;

for (int i=0; i<nums.size(); i++)
{
{
result.push_back(i+1);
}
}

return result;
}
http://fisherlei.blogspot.com/2013/03/leetcode-two-sum-solution.html
O(N^2)
 ```public static int[] twoSum(int[] numbers, int target) { int[] ret = new int[2]; for (int i = 0; i < numbers.length; i++) { for (int j = i + 1; j < numbers.length; j++) { if (numbers[i] + numbers[j] == target) { ret[0] = i + 1; ret[1] = j + 1; } } } return ret; }```
GoLang:
https://github.com/Max-Liu/Leetcode-in-golang/blob/master/two-sum/main.go
func main() {
nums := []int{2, 7, 11, 15, 18, 22}
fmt.Println((twoSum(nums, 37)))
}
func twoSum(nums []int, target int) (index1, index2 int) {
for i1, _ := range nums {
for i2 := i1 + 1; i2 < len(nums); i2++ {
if nums[i1]+nums[i2] == target {
index1 = i1 + 1
index2 = i2 + 1
}
}
}
return index1, index2
}

Arraylist<Pair> printPairSums(int[] array, int sum) {
Arraylist<Pair> result= new Arraylist<Pair>();
HashMap<Integer, Integer> unpairedCount = new HashMap<Integer, Integer>();
for (int x : array) {
int complement = sum - x;
if (unpairedCount.getOrDefault(complement, 0) > 0) {
adjustCounterBy(unpairedCount, complement, -1); // decrement complement
} else {
adjustCounterBy(unpairedCount, x, 1); // increment count
}
}
return result;
}

https://reeestart.wordpress.com/2016/06/06/23k-sum/
 `// O(n) time, O(n) space` `public` `List> twoSum(``int``[] nums, ``int` `target) {` `  ``List> result = ``new` `ArrayList<>();` `  ``if` `(nums == ``null` `|| nums.length == ``0``) {` `    ``return` `result;` `  ``}` `  `  `  ``Map> map = ``new` `HashMap<>();` `  ``Set set = ``new` `HashSet<>();` `  ``for` `(``int` `i = ``0``; i < nums.length; i++) {` `    ``map.putIfAbsent(nums[i], ``new` `ArrayList<>());` `    ``map.get(nums[i]).add(i);` `  ``}` `  `  `  ``for` `(``int` `i = ``0``; i < nums.length; i++) {` `    ``int` `toFind = target - nums[i];` `    ``if` `(map.containsKey(toFind)) {` `      ``for` `(``int` `j : map.get(toFind)) {` `        ``if` `(i != j && !set.contains(nums[i]) && !set.contains(nums[j])) {` `          ``result.add(``new` `ArrayList<>(Arrays.asList(nums[i], nums[j])));` `          ``set.add(nums[i]);` `          ``set.add(nums[j]);` `        ``}` `      ``}` `    ``}` `  ``}` `  `  `  ``return` `result;` `}`
I was asked what if duplicates exists.. How do we handle this?
My original thought is worst case nums = [1,1,1,1] target is 2
I think you can doing the same solution that in the case without duplicates, but you need another auxiliary variable to know if the number is duplicate (in this case only remember 2 different index).
something like:
``````x = num[i]
if ((target - x == x) and isDuplicate(x))
return {i, idx_previous[x]}``````
http://www.cnblogs.com/aprilyang/p/6701586.html
Given an array of integers, find how many `unique pairs` in the array such that their sum is equal to a specific target number. Please return the number of pairs.
Example
Given nums = `[1,1,2,45,46,46]`, target = `47`
return `2`
1 + 46 = 47
2 + 45 = 47
```    public int twoSum(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return 0;
}
Arrays.sort(nums);
int start = 0;
int end = nums.length - 1;
int count = 0;
while (start < end) {
if (nums[start] + nums[end] < target) {
start++;
} else if (nums[start] + nums[end] > target) {
end--;
} else {
count++;
start++;
end--;
while (start < end && nums[start] == nums[start - 1]) {
start++;
}
while (start < end && nums[end] == nums[end + 1]) {
end--;
}
}
}
return count;
}```

```    public int twoSum6(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return 0;
}
Arrays.sort(nums);
int start = 0;
int end = nums.length - 1;
int count = 0;
while (start < end) {
if (start > 0 && nums[start] == nums[start - 1]) {
start++;
continue;
}
if (end < nums.length - 1 && nums[end] == nums[end + 1]) {
end--;
continue;
}
if (nums[start] + nums[end] < target) {
start++;
} else if (nums[start] + nums[end] > target) {
end--;
} else {
count++;
start++;
}
}
return count;
}```