专栏首页曌的晓痴LeetCode - 4数之和

LeetCode - 4数之和

今天才发现,上周在钉钉上面加我的阿里同学,就是给我发offer的HR,而我当时并不知道,只知道去骚扰其他的HR问结果。

言归正传,这题是LeetCode第18题,中等难度,估计是我4月按顺序刷题的最后几题了...

原题地址:https://leetcode-cn.com/problems/4sum/

题目描述

给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 target 相等?找出所有满足条件且不重复的四元组。

注意:

答案中不可以包含重复的四元组。

示例:

给定数组 nums = [1, 0, -1, 0, -2, 2],和 target = 0。

满足要求的四元组集合为:

[

[-1, 0, 0, 1],

[-2, -1, 1, 2],

[-2, 0, 0, 2]

]

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/4sum

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路:

我这种力量(暴力,无智慧)型选手,只能使用最笨的方法啦。本题采用的策略是固定两个指针,移动两个指针的方案。

  1. 先排序,排序之后,才好指针移动啊
  2. 确定两个固定指针分别指定i和j,i范围从0到倒数第四个,j从i+1到倒数第三个,注意跳过相同的值
  3. 然后确定两个移动指针l和r,l从j+1往右移动,r从最右边往左移动
  4. 计算nums[i] + nums[j] + nums[l] + nums[r]是否等于target(一开始审题没清楚,所以计算了是否等于0,导致解答错误),如果大了,就减小r;小了就增加l

中文官网题解:

https://leetcode-cn.com/problems/4sum/solution/

个人题解:

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
         Arrays.sort(nums);
        Set<List<Integer>> sets = new HashSet<>();
        for (int i = 0; i < nums.length - 3; i++) {
            for (int j = i + 1; j < nums.length - 2; j++) {
                if (i != 0 && nums[i] == nums[j] && nums[i] == nums[i - 1]) {
                    continue;
                }
                int l = j + 1;
                int r = nums.length - 1;
                while (l < r) {
                    int sum = nums[i] + nums[l] + nums[r] + nums[j];
                    if (sum == target) {
                        sets.add(Arrays.asList(nums[i], nums[l], nums[r], nums[j]));
                        l++;
                        r--;
                    } else if (sum > target) {
                        r--;
                        while (l < r && nums[r] == nums[r + 1]) {
                            r--;
                        }
                    } else {
                        l++;
                        while (l < r && nums[l] == nums[l - 1]) {
                            l++;
                        }
                    }
                }
            }
        }
        return new ArrayList<>(sets);
    }
}

结果:

可以很明显的看到,这个方法并不是很好,只超过了18%的人...

本文分享自微信公众号 - 曌的晓痴(gh_543795945efe),作者:zxyAnkh

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-06-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode-下一个排列

    感觉从之前的题目开始写起来的话,会需要一定的时间去思考当时为什么这么写,那么每次写都是重新思考,除非进度能够赶上最新的刷题进度,所以决定从最新的开始往前写......

    晓痴
  • LeetCode - 存在重复元素

    原题地址:https://leetcode-cn.com/problems/contains-duplicate/

    晓痴
  • LeetCode - 搜索插入位置

    LeetCode第35题,难度简单。接下去的题目可能会慢慢变成两三年之前做的题目了....清完库存我再接着解题,写题解...

    晓痴
  • python实现给定一个数和数组,求数组

    给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。

    py3study
  • 283 Move Zeroes

    /** * 题意:将0挪到末尾,并且不改数组中原有元素的顺序 * 解析:找到0元素,然后寻找其后面非0的元素,进行交换位置 * @param {numbe...

    用户1624346
  • Leetcode 15 三数之和(双指针,去重)

    给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三...

    glm233
  • Array - 508. Wiggle Sort

    Given an unsorted array nums, reorder it in-place such that

    用户5705150
  • Q189 Rotate Array

    Rotate an array of n elements to the right by k steps. For example, with n = 7 a...

    echobingo
  • 【剑指Offer】调整数组顺序使奇数位于偶数前面

    输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。

    小新哟
  • LeetCode-31-Next-Permutation

    这个排序主要是有两种情况,一个是类似于3 1 2这样的情况,直接从后往前找到第一个nums[i]<nums[i-1]的,然后把i记下来,再与后面第一个小于i的k...

    小二三不乌

扫码关注云+社区

领取腾讯云代金券