第七色在线视频,2021少妇久久久久久久久久,亚洲欧洲精品成人久久av18,亚洲国产精品特色大片观看完整版,孙宇晨将参加特朗普的晚宴

為了賬號安全,請及時綁定郵箱和手機立即綁定

每天AC系列(一):三數(shù)之和

標簽:
算法

1 题目

LeetCode第15题,难度中等,题目描述:

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

注意:答案中不可以包含重复的三元组。

在这里插入图片描述

2 解法

什么也不管先来个O(n3):

for(int i=0;i<nums.length;++i)
{
    for(int j=i+1;j<nums.length;++j)
    {
        for(int k=j+1;k<nums.length;++k)
        {
            if(nums[i]+nums[j]+nums[k] == 0)
            {
                ArrayList<Integer> arrayList = new ArrayList<>();
                arrayList.add(nums[i]);
                arrayList.add(nums[j]);
                arrayList.add(nums[k]);
                result.add(arrayList);
            }
        }
    }
}

在这里插入图片描述

well.

3 优化

上面暴力算法的思想就是单纯三个循环,优化的方法可以考虑降低一个循环,使用"双指针"的思想,首先对数组进行排序,然后一开始固定一个数,然后让两个指针一个指向这个数的右区间的起点,一个指向终点,不断计算这三个值的和,根据得出的和移动左指针或者右指针,一共三种情况:

  • 和等于0,同时移动左右指针,两者向中间方向移动.
  • 和大于0,说明取值过大,需要把右指针向左移动.
  • 和小于0,说明取值过小,需要把左指针向右移动.

基于以上的三种情况,写出了如下代码:

List<List<Integer>> result = new ArrayList<>();
if (nums.length == 3 && nums[0] + nums[1] + nums[2] == 0)
    result.add(Arrays.asList(nums[0], nums[1], nums[2]));
else if (nums.length > 3) 
{
    Arrays.sort(nums);
    Set<List<Integer>> resultSet = new HashSet<>();
    for (int i = 0; i < nums.length - 2 && nums[i] <= 0; ++i) 
    {
        int left = i + 1;
        int right = nums.length - 1;
        while (left < right) 
        {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) 
            {
                if (!resultSet.contains(Arrays.asList(nums[i], nums[left], nums[right]))) 
                    resultSet.add(Arrays.asList(nums[i], nums[left], nums[right]));
                --right;
                ++left;
            } 
            else if (sum > 0)
                --right;
            else
                ++left;
        }
    }
    result.addAll(resultSet);
}

首先判断数组的长度是否大于等于3,小于3的话直接返回一个空List,等于3判断是否这三个数之和为0,大于3的话,首先排序,接着需要确保被确定的相对不移动的数为负数,这样的话剩下两个数的和才有可能为正数,否则的话会造成全部都是正数还要进行判断的局面.接着计算left指针与right指针的值,一直判断直到两指针相遇.

4 提交

在这里插入图片描述

AC!

5 完整代码

點擊查看更多內(nèi)容
TA 點贊

若覺得本文不錯,就分享一下吧!

評論

作者其他優(yōu)質(zhì)文章

正在加載中
JAVA開發(fā)工程師
手記
粉絲
5
獲贊與收藏
30

關(guān)注作者,訂閱最新文章

閱讀免費教程

  • 推薦
  • 評論
  • 收藏
  • 共同學習,寫下你的評論
感謝您的支持,我會繼續(xù)努力的~
掃碼打賞,你說多少就多少
贊賞金額會直接到老師賬戶
支付方式
打開微信掃一掃,即可進行掃碼打賞哦
今天注冊有機會得

100積分直接送

付費專欄免費學

大額優(yōu)惠券免費領

立即參與 放棄機會
微信客服

購課補貼
聯(lián)系客服咨詢優(yōu)惠詳情

幫助反饋 APP下載

慕課網(wǎng)APP
您的移動學習伙伴

公眾號

掃描二維碼
關(guān)注慕課網(wǎng)微信公眾號

舉報

0/150
提交
取消