Not AC solution without sorting


  • 0
    S

    The time is still O(n^2). But not AC..

    class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> resultList = new ArrayList<>();
            Set<String> visited = new HashSet<>();
            Set<Integer> set;
            for (int i = 0; i < nums.length - 2; i++) {
                int target = - nums[i];
                set = new HashSet<>();
                for (int j = i+1; j < nums.length; j++) {
                    if (set.contains(nums[j])) {
                        Integer[] result = new Integer[]{nums[i], nums[j], target-nums[j]};
                        Arrays.sort(result);
                        if (!visited.contains(getArrayString(result))) {
                            visited.add(getArrayString(result));
                            resultList.add(Arrays.asList(result));
                        }
                    } else {
                        set.add(target - nums[j]);
                    }
                }
            }
            return resultList;
        }
        
        private String getArrayString(Integer[] arr) {
            String result = "";
            for (int n : arr) {
                result = result + n +"#";
            }
            return result;
        }
    }
    

Log in to reply
 

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