Tuesday, March 10, 2015

Find sum


Given an array with numbers, your task is to find 4 numbers that will satisfy this equation: 
A + B + C = D

Similar to LeetCode's four sum.

I let the the outmost iteration starts from n.length - 1, which is the D in the equation. The next iteration starts from 0, which represents A, and then n[j + 1] as B and n[i - 1] as C.

import java.util.*;
public class SumNumbers {
 public static List> findSum(int[] n){
  List> rst = new ArrayList>();
  if(n == null || n.length == 0)
   return rst;
  Arrays.sort(n);
  for(int i = n.length - 1; i >= 3; i--){
   if(i != n.length - 1 && n[i] == n[i + 1])
    continue;
   for(int j = 0; j < i; j++){
    if(j != 0 && n[j] == n[j - 1])
     continue;
    int first = j + 1;
    int second = i - 1;
    while(first < second){
     int sum = n[first] + n[second] + n[j];
     if(sum == n[i]){
      List curr = new ArrayList();
      curr.add(n[j]);
      curr.add(n[first]);
      curr.add(n[second]);
      curr.add(n[i]);
      rst.add(curr);
      first++;
      second--;
      while(first < second && n[first] == n[first - 1])
       first++;
      while(first < second && n[second] == n[second + 1])
       second--;
     }
     else if (sum < n[i])
      first++;
     else
      second--;
    }
   }
  }
  return rst;
 }

 public static void main(String[] args) {
  int[] n = {1, 9, 8, 7, 0, 9, 1, 2, 2, 0, 8, 6};
  for(List sum : findSum(n)){
   for(int i : sum){
    System.out.print(i + " ");
   }
   System.out.println();
  }

 }

}


In case you are interested, here is the 4sum code.


public List> fourSum(int[] num, int target) {
        List> rst = new ArrayList>();
        if(num == null || num.length == 0)
            return rst;
        Arrays.sort(num);
        for (int i = 0; i < num.length - 3; i++){
            if (i != 0 && num[i] == num[i - 1])
                continue;
            for(int j = i + 1; j < num.length - 2; j++){
                if(j != i + 1 && num[j] == num[j - 1])
                    continue;
                int third = j + 1;
                int forth = num.length - 1;
                while(third < forth){
                    int sum = num[i] + num[j] + num[third] + num[forth];
                    if(sum == target){
                        List list = new ArrayList();
                        list.add(num[i]);
                        list.add(num[j]);
                        list.add(num[third]);
                        list.add(num[forth]);
                        rst.add(list);
                        third++;
                        forth--;
                        while(third < forth && num[third - 1] == num[third])
                            third++;
                        while(third < forth && num[forth] == num[forth + 1])
                            forth--;
                    }
                    else if(sum < target)
                        third++;
                    else
                        forth--;
                }
            }
        }
     return rst;   
    }

No comments:

Post a Comment