2 Sum 3 Sum 3 Sum Closest 4 Sum

Leave a comment

August 21, 2016 by oneOokay

2 Sum:

除了普通的two pointers的方法以外,另一个较为高效的方法是用hashmap。

public class Solution {
    public int[] twoSum(int[] nums, int target) {
      Map<Integer, Integer> hash = new HashMap<Integer, Integer> ();
      int[] result = new int[2];
      for (int i = 0; i < nums.length; ++i) {
        if (hash.containsKey(target - nums[i])) {
          result[0] = hash.get(target - nums[i]) + 1;
          result[1] = i + 1;
          break;
        }
        hash.put(nums[i], i);
      }
      return result;
    }

3 Sum:

此题难点在除重吧,比较容易产生bug,除此以外没有太多其他的点。

然后我之前写的是把需要重复用到的变量写在for loop之外,随后就reuse,但是写出来的代码比较难看,一堆initialization的在前面。于是不reuse了,每次new 一个变量,代码看起来比较好看一些。

先sort array,再一个for-loop,外加two pointers.

public ArrayList<ArrayList<Integer>> threeSum(int[] numbers) {
// write your code here
if (numbers == null || numbers.length <= 2) {
return null;
}
ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
Arrays.sort(numbers);
for (int i = 0; i < numbers.length – 2; i ++) {
if (i != 0 && numbers[i] == numbers[i – 1]) { //除重
continue;

int start = i + 1;
int end = numbers.length – 1;
while (start < end) {
int sum = numbers[i] + numbers[start] + numbers[end];
if (sum == 0){
ArrayList<Integer> result = new ArrayList<Integer>();
result.add(numbers[i]);
result.add(numbers[start]);
result.add(numbers[end]);
results.add(result);
start ++;
end –;
while (start < end && numbers[start] == numbers[start – 1]) { //除重
start ++;
}
while (start < end && numbers[end] == numbers[end + 1]){//除重
end –;
}
}else if (sum < 0) {
start ++;
}else {
end –;
}
}
}
return results;
}

3 Sum closest:

注意找到差值更小的绝对值的时候,不能移动pointers,而应该等到具体判断值大于还是小于target。

public int threeSumClosest(int[] nums, int target) {
// write your code here
if (nums == null || nums.length < 3) {
return 0;
}

Arrays.sort(nums);
int result = nums[0] + nums[1] + nums[2];
int diff = Math.abs(result – target);
for (int i = 0; i < nums.length; i ++) {
int start = i + 1;
int end = nums.length – 1;
while (start < end) {
int sum = nums[i] + nums[start] + nums[end];
if(sum == target) {
return target;
}
if(Math.abs(sum – target) < Math.abs(result – target))
{
result = sum; //这里不能start ++; end–;
}

if(sum > target) {
end –;
}else {
start ++;
}
}
}
return result;
}

 

4 Sum: 

九章的答案基本上就是延续了3 Sum的算法,两个for-loops, i, j, 外加two pointers left & right,相同的除重方法得到答案。有一点点无聊。

可以看这个人的4 sum的解法:http://bangbingsyb.blogspot.com/2014/11/leetcode-4sum.html,具体会在k sum I II 里面写

public ArrayList<ArrayList<Integer>> fourSum(int[] nums, int target) {
/* your code */
ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
if (nums == null || nums.length < 4) {
return results;
}
Arrays.sort(nums);
if (target < nums[0] || target > nums[nums.length – 1]) {
return results;
}
for (int i =0; i < nums.length – 3; i ++) {
if (i != 0 && nums[i] == nums[i – 1]) {
continue;
}
for (int j = i + 1; j < nums.length – 2; j ++) {
if (j != i + 1 && nums[j] == nums[j – 1]) {
continue;
}
int left = j + 1;
int right = nums.length – 1;
while (left < right) {
int sum = nums[i] + nums[j] + nums[left] + nums[right];
if (sum == target) {
ArrayList<Integer> tmp = new ArrayList<Integer>();
tmp.add(nums[i]);
tmp.add(nums[j]);
tmp.add(nums[left]);
tmp.add(nums[right]);
results.add(tmp);
left ++;
right –;
while (left < right && nums[left] == nums[left – 1]) {
left ++;
}
while (left < right && nums[right] == nums[right + 1]) {
right –;
}
} else if (sum < target) {
left ++;
} else {
right –;
}}}}
return results;
}

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: