搜索
您的当前位置:首页正文

基础算法练习

来源:二三娱乐

题目:三数之和

给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。
注意:答案中不可以包含重复的三元组
示例: 例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],
 满足要求的三元组集合为:
[ [-1, 0, 1],
 [-1, -1, 2]]

Java 的实现方式:
public List<List<Integer>> threeSum(int[] nums) {
     // 只有插入操作,创建链表提升效率
     List<List<Integer>> lists = new LinkedList<>();
    //先进行排序操作, 
       Arrays.sort(nums);
       int l = nums.length;
       int truel=l-2; // 循环真正的次数
       for (int i = 0; i < truel;i++) {
           int a = nums[i]; // 当前的
           int mid = i + 1;  // 设置下一个
           int end = l - 1;// 最后一个,由于我们前面排序之后前后相加的回出现三种情况 0, >0 ,<0, 
           while (mid < end) { // i位置数据确定一轮循环是否完成
               int b = nums[mid];
               int c = nums[end];
               if (a + b + c > 0) { // 此种情况说明end位置上的数据远大于i 与mid之和,我们只需要从后向前遍历即可
                   end--;
                  // 由于数组中可能出现重复的数据,计算一次之后,过滤到重复数据,保证最后的数组中不出现重复的集合
                   while (mid < end && nums[end] == nums[end + 1]) {
                       end--;
                   }
               } else if (a + b + c < 0) { // 此种情况与第一种相反的处理即可
                   mid++;
                   while (mid < end && nums[mid] == nums[mid - 1]) {
                       mid++;
                   }
               } else { // 等于0的情况
                   List<Integer> list = new ArrayList<>(3);
                   list.add(a);
                   list.add(nums[mid]);
                   list.add(nums[end]);
                   lists.add(list);
                   mid++;
                   end--;
                   // 跳过相同的数据
                   while (mid < end && nums[mid] == nums[mid - 1]) {
                     mid++;
                   }
                   while (mid < end && nums[end] == nums[end + 1]) {
                       end--;
                   }
               }
          }
           // 第一轮循环结束,继续查找下一个坐标,且保证数据与上次处理的不相同
           while (i < truel  && nums[i+1] == nums[i]) {
               i++;
           }   
       }
       return lists;
   }

基础算法的练习,是进入大厂的必要的知识积累。
共勉

Top