题解 | #牛牛的三元组问题#

牛牛的三元组问题

https://www.nowcoder.com/practice/72c6d735fb1144a2ba162976a4510839

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型二维数组
     */
    public int[][] findTriplets (int[] nums) {
        // write code here
        List<List<Integer>> result = new ArrayList<>();

        // 首先对数组进行排序
        Arrays.sort(nums);

        int n = nums.length;

        for (int i = 0; i < n - 2; i++) {
            // 避免重复三元组
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int left = i + 1;
            int right = n - 1;

            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];

                if (sum == 0) {
                    // 找到一个特殊三元组
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));

                    // 移动左右指针,避免重复元素
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }

                    left++;
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        int[][] arrayResult = convertListToArray(result);
        return arrayResult;
    }

    private int[][] convertListToArray(List<List<Integer>> result) {
        int numRows = result.size();
        int[][] arrayResult = new
        int[numRows][3]; // 假设每个三元组都有3个元素

        for (int i = 0; i < numRows; i++) {
            List<Integer> triplet = result.get(i);
            for (int j = 0; j < 3; j++) {
                arrayResult[i][j] = triplet.get(j);
            }
        }

        return arrayResult;
    }
}
  1. 首先,我们对整数数组进行排序,这有助于在后续查找中进行优化,以避免重复元素的影响。
  2. 然后,我们使用两个循环来遍历数组,外层循环固定第一个元素,内层循环使用双指针(left和right)来查找满足和为零的三元组。
  3. 在内层循环中,我们计算当前三元组的和(sum),如果和等于零,则找到一个特殊三元组,将其添加到结果列表中。
  4. 接着,我们移动左右指针,以避免重复元素的干扰,同时继续寻找下一个三元组。
  5. 如果和小于零,我们增加左指针;如果和大于零,我们减小右指针。
  6. 在遍历完整个数组后,我们返回结果列表,其中包含所有满足条件的特殊三元组,最后转为二维数组。
全部评论

相关推荐

好想摆:一想到我苦苦追求的迪子私下里却是985的马子,我的心就在滴血😭😭😭
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 10:39
一个证都没&nbsp;我能填什么
程序员小白条:别人有,你为什么没有,还是这个道理,社会就是比较,竞争,淘汰,你要安逸,那么就要做好淘汰的准备
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务