讨论/《中级算法》 - 三数之和/
《中级算法》 - 三数之和
共 17 个回复

下面竟没有初级算法中那个男人的身影了

7

执行用时:21 ms, 在所有 Java 提交中击败了97.86%的用户
内存消耗:42.8 MB, 在所有 Java 提交中击败了15.64%的用户

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
          if(nums.length < 3){
            return new ArrayList<>();
        }
        //暴力破解需要O(n^3),然后我们看到要去重,可以用排序的方法避免重复
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        for(int i = 0; i < nums.length;i++) {
            // 因为排过序了,所以num[i]>0后面肯定不符合要求了
            if(nums[i] > 0 ){
                break;
            }
            // 重复的就不要走了
            if(i > 0 && nums[i] == nums[i-1]){
                continue;
            }
            //采用双指针头尾各一个,往中间走
            int left = i + 1;
            int right = nums.length - 1;
            while(left < right){
                if(nums[i] + nums[left] + nums[right] > 0){
                    right--;
                }else if(nums[i] + nums[left] + nums[right] < 0){
                    left++;
                }else {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    result.add(list);
                    //要继续走下去,可能还有
                    right--;
                    left++;
                    // 重复的不要走了
                    while(left < right && nums[left] == nums[left-1]){
                        left++;
                    }
                    while(left < right && nums[right+1] == nums[right]){
                        right--;
                    }

                }
            }
        }
        return  result;
    }
}
2

用哈希表的话主要是去重操作不好想

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        //排序方便去重
        Arrays.sort(nums);
        //记录每个数的下标
        Map<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
        for(int i = 0; i < n; ++i) {
            hashMap.put(nums[i], i);
        } 
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        for(int i = 0; i < n; ++i) {
            int target = -nums[i];
            //去重
            if(i > 0 && nums[i] == nums[i-1]) {
                continue;
            }
            for(int j = i + 1; j < n; ++j) {
                //去重
                if(j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                Integer index = hashMap.get(target - nums[j]);
                //看存不存在target
                if(index != null && index > j) {
                    res.add(new ArrayList<Integer>(Arrays.asList(nums[i], nums[j], target - nums[j])));
                }
            }
        }
        return res;
    }
}
1
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        if (nums.size() < 3)
            return {};
        sort(nums.begin(), nums.end());
        int target = 0;
        vector<vector<int>> result;
        for (int i = 0; i < nums.size()-2 && nums[i] <= 0; ++i) {
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            target = -nums[i];
            int j = i+1, k = nums.size()-1;
            while (j < k) {
                if (nums[j]+nums[k] > target) k--;
                else if (nums[j]+nums[k] < target) j++;
                else {
                    result.push_back({nums[i],nums[j],nums[k]});
                    ++j, --k;
                    while (j < k && nums[j] == nums[j-1]) j++;
                    while (j < k && nums[k] == nums[k+1]) k--;
                }
            }
        }
        return result;
    }
};
1

三个测试用例超时,但是怎么解决暂时没想到,求大佬指教

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> vecs;
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size();i++){
            for(int j=i+1;j<nums.size();j++){ 
                for(int k=j+1;k<nums.size();k++){
                    if(nums[i]+nums[j]+nums[k]==0){
                        vecs.push_back({nums[i],nums[j],nums[k]});
                    }
                    while(k+1<nums.size()&&nums[k]==nums[k+1]){
                        k++;
                    }
                }
                while(j+1<nums.size()&&nums[j]==nums[j+1]){
                    j++;
                }
            }
            while(i+1<nums.size()&&nums[i]==nums[i+1]){
                i++;
            }
        }
        return vecs;
    }
};

超时,太痛苦了
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> a=new ArrayList<List<Integer>>();
if(nums.length==0)
return a;
Arrays.sort(nums);
int a1=nums[0]-1,a2=0,a3=0;
for(int i=0;i<nums.length-2;i++)
{
if(nums[i]>0)
break;
if(nums[i]==a1)
continue;
a1=nums[i];
a2=nums[0]-1;
for(int j=i+1;j<nums.length-1;j++)
{
if(nums[j]==a2)
continue;
a2=nums[j];
a3=nums[0]-1;
for(int k=j+1;k<nums.length;k++)
{
if(nums[k]==a3)
continue;
a3=nums[k];
if(nums[i]+nums[j]+nums[k]==0)
{
List<Integer> b=new ArrayList<Integer>();
b.add(nums[i]);
b.add(nums[j]);
b.add(nums[k]);
a.add(b);
break;

                }
            }
        }
    }
    return a;

}

}

是的,写错了

第一个continue 改成 break 更优

很明显超时啊

你没有考虑输入数组的长度小于3的情况