Java solution that deal with integer overflow


  • 0
    A

    Try this input : [2147483647,0,1,12,-1,-4,-10,-1, 0, 1, 2, -1, 2147483647]
    OJ is wrong and return [[-1,-1,2],[-1,0,1],[2,2147483647,2147483647]]

    Just use long for sums :

       public static List<List<Integer>> threeSum(int[] num) {
        Arrays.sort(num);
        List<List<Integer>> res = new ArrayList<>();
        for (int i=0; i<num.length-2; i++) {
            if (i == 0 || num[i] != num[i - 1]) {
                int lo = i + 1;
                int hi = num.length - 1;
                long sum = 0 - num[i];
                while (lo < hi) {
                    if (sum == (long) num[lo] + (long) num[hi]) {
                        List<Integer> list = new ArrayList(3);
                        list.add(num[i]);
                        list.add(num[lo]);
                        list.add(num[hi]);
                        res.add(list);
                        while (lo < hi && num[lo] == num[lo+1]) lo++;
                        while (lo < hi && num[hi] == num[hi-1]) hi--;
                        lo++; hi--;
                    } else if (num[lo] + num[hi] < sum) lo++;
                    else hi--;
                }
            }
        }
        return res;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.