东风不来
三月的柳絮不飞

Leetcode:三数之和 Java 实现 讲解非常详细

1. 题目:

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

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

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],

满足要求的三元组集合为:
[
[-1, 0, 1],
[-1, -1, 2]
]

2. 解题思路

(1)先考虑将 nums 进行排序;
(2)将 nums[i] 作为第一个加数,从 i+1 到 nums.length – 1 之间初始化两个指针 j、k ,为了避免有重复的情况,当 nums[i] == nums[i-1] ,说明有重复的情况,开始下一个循环;
(3)如果 num[i] + num[j] + num[k] > target,说明加多了,让 k-–;
(4)如果 num[i] + num[j] + num[k] < target,说明加少了,让 j++;
(5)如果等于 target ,说明符合条件,将这一组解加到集合中,这时也应该避免第二个加数和第三个加数重复的情况。

3. Java 实现

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class threeSum {
    public List<List<Integer>> threeSum_fuction(int[] nums,int target){
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        for(int i = 0;i < nums.length-2;i++)
        {
            if(i>0&&nums[i] == nums[i-1])
                continue;
            int j = i + 1;
            int k = nums.length - 1;
            while(j < k){
                if(nums[i] + nums[j] + nums[k] == target)
                {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[j]);
                    list.add(nums[k]);
                    result.add(list);
                    while(j<k&&nums[j]==nums[j+1])
                        j++;
                    while(j<k&&nums[k]==nums[k-1])
                        k--;
                    j++;
                    k--;
                }
                else if(nums[i] + nums[j] + nums[k] < target)
                {
                    j++;
                }
                else if(nums[i] + nums[j] + nums[k] > target)
                {
                    k--;
                }
            }
        }
        return result;
    }

    public static void main(String[] args)
    {
        int[] nums = new int[]{-1, 0, 1, 0, 1, 1};
        int target = 3;
        threeSum S = new threeSum();
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        result = S.threeSum_fuction(nums,target);
        System.out.println(result);
    }
}

赞(1) 打赏
未经允许不得转载:文字咖 » Leetcode:三数之和 Java 实现
分享到:

评论 抢沙发

8 + 8 =
  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏