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