Clean, straightforward solution using 2sum


  • 4
    O
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        vector<vector<int>> results;
        sort(nums.begin(), nums.end());
        
        for(int i=0; i<nums.size(); i++)
        {
            twoSum(i, nums, results, 0-nums[i]);
            
            while(i<nums.size()-1 && nums[i] == nums[i+1])
                i++;
        }
        return results;
    }
    
    void twoSum(int index, vector<int>&nums, vector<vector<int>>& results, int sum)
    {
        unordered_map<int, int> record;
        
        for(int i=index+1; i<nums.size(); i++)
        {
            if(record.find(nums[i]) == record.end())
                record[sum-nums[i]] = nums[i];
            else
            {   
                vector<int> vec;
                vec.push_back(nums[index]);
                vec.push_back(record[nums[i]]);
                vec.push_back(nums[i]);
                results.push_back(vec);
                
                while(i<nums.size()-1 && nums[i] == nums[i+1])
                    i++;
            }
        }
    }

  • 0
    H

    The same in Java, but TLE, don't know why

    public class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            Arrays.sort(nums);
            List<List<Integer>> res = new ArrayList<>();
            for(int i = 0; i < nums.length-2; i++){
                int target = - nums[i];
                if(target<0) break;
                Map<Integer, Integer> m = new HashMap<>();
                for(int ii = i+1; ii < nums.length; ii++){
                    System.out.println(ii);
                    if(m.get(nums[ii]) != null){
                        res.add(Arrays.asList(nums[i], nums[m.get(nums[ii])], nums[ii]));
                    } else{
                        m.put(target - nums[ii], ii);
                        while(ii+1 < nums.length && nums[ii+1] == nums[ii]) ii++;
                    }
                }
            }
            return res;
        }
    }

  • 0
    Y

    Don print out anything! The io time cost can be significant.


Log in to reply
 

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