超实用的算法小技巧

本篇文章我们将介绍一些超级实用的算法小技巧，灵活使用这些算法小技巧可以帮助我们更好的解决遇到的问题，让我们的时间复杂度，空间复杂度大大降低，有效的提高我们的编程能力。

1 严格定义函数名称，出入参

我们在一开始拿到算法题，读懂题之后，就需要根据题意定义我们的函数名称，以及入参，函数的返回类型。日常的企业项目开发也是一样，我们在拿到需求之后，需要去定义接口，入参，出参。

我们一定要给处理函数起一个能够明确表达函数功能的名字比如：排序sort，搜索search，统一用英文表示（入参也是如此）。

leetcode技巧： 变量名称定义简单，可以提高算法执行速度，这也是在好多人在刷leetcode参数定义不那么规范的原因，往往在周赛或者一些比赛中一点点优势，就能助我们取得胜利。

2 严进宽出，边界判断

严进宽出就是说我们要对算法的入参进行严格的验证，比如我们经常要对数组、字符串进行非空校验，还有一些需要对边界值进行校验。

对于不符合规范的直接返回，很好的把控边界也可提升我们的算法效率。

笔试小技巧： 优雅严格的边界值判断，往往能给面试官留下很好的印象。

// 入参校验

if (nums == null || nums.length == 0) {

    return -1;

}

// 边界值（不相等时，我们让左边指针移动到二分处，并且+1就很细节，因为中间点已经不符合，所以我们+1可以少循环一次）

while (l <= r) {

    mid = l + (r - l) / 2;

    if (nums[mid] == target) {

        return mid;

    } else if (nums[mid] < target) {

        l = mid + 1;

    } else if (nums[mid] > target) {

        r = mid - 1;

    }

}

3 暴力解法

没有经过算法训练的同学，一般在解决算法问题时，只能想到暴力解法，常常就是多层嵌套函数，定义额外的空间。

往往时间复杂度都是O(N)、O(N²) 虽然也能解决算法问题，但是往往因为算法的执行效率过低，代码不够优雅让Offer与我们失之交臂。

不过暴力解法虽然效率不高，但是是我们必须掌握的，写出来永远比什么都写不出来要强的多，暴力解法就要求我们灵活应用每种数据结构的遍历，并加入条件判断逻辑。

以下几个技巧则可以帮助我们优化算法，提供算法的执行效率。

4 双指针（Two Pointers）

双指针是一种算法小套路，我们在好多地方可以见到双指针的妙用，比如二分查找，确定链表是否成环等，接下来我们就来一起探究一下双指针的妙用。

双指针一般有以下几种形式。

• 普通双指针

  两个指针往同一个方向移动

      /**
  
       * 冒泡排序
  
       * @param nums
  
       */
  
      public static void sort(int [] nums) {
  
          if (nums == null || nums.length == 0) {
  
              return;
  
          }
  
          int temp = 0;
  
          for (int i = 0; i < nums.length - 1; i++) {
  
              for (int j = i + 1; j < nums.length; j++) {
  
                  if (nums[i] > nums[j]) {
  
                      temp = nums[i];
  
                      nums[i] = nums[j];
  
                      nums[j] = temp;
  
                  }
  
              }
  
          }
  
      }
  

• 对撞双指针

  两个指针从两端向对方移动

  /**
  
   * 力扣704 二分查找
  
   * 二分查找算法是借助二分的思想，结合双指针来实现的一种搜索算法
  
   * @author zhj
  
   */
  
  public class Test704 {
  
      public static void main(String[] args) {
  
          int[] nums = {-1, 0, 3, 5, 9, 12};
  
          int index = search(nums, 5);
  
          System.out.println(index);
  
      }
  
  
      private static int search(int[] nums, int target) {
  
          if (nums == null || nums.length == 0) {
  
              return -1;
  
          }
  
          int l = 0;
  
          int r = nums.length - 1;
  
          int mid;
  
          while (l <= r) {
  
              mid = l + (r - l) / 2;
  
              if (nums[mid] == target) {
  
                  return mid;
  
              } else if (nums[mid] < target) {
  
                  l = mid + 1;
  
              } else if (nums[mid] > target) {
  
                  r = mid - 1;
  
              }
  
          }
  
          return -1;
  
      }
  
  }
  

• 快慢双指针

  慢指针+快指针 解决环形链表问题

  /**
  
   * 力扣 141 环形链表
  
   * 给定一个链表，判断链表中是否有环
  
   * @author zhj
  
   */
  
  public class Test141 {
  
      public static void main(String[] args) {
  
          ListNode node = new ListNode(1);
  
          ListNode node1 = new ListNode(2);
  
          ListNode node2 = new ListNode(3);
  
          ListNode node3 = new ListNode(4);
  
          ListNode node4 = new ListNode(5);
  
          node.next = node1;
  
          node1.next = node2;
  
          node2.next = node3;
  
          node3.next = node4;
  
          node4.next = node2;
  
          System.out.println(isRing(node));
  
      }
  
  
      private static boolean isRing(ListNode node) {
  
          if (node == null || node.next == null) {
  
              return false;
  
          }
  
          ListNode s = node;
  
          ListNode f = node;
  
          while (f != null && f.next != null) {
  
              s = s.next;
  
              f = f.next.next;
  
              if (s == f) {
  
                  return true;
  
              }
  
          }
  
          return false;
  
      }
  
  }
  

5 滑动窗口

滑动窗口也是一种算法小技巧，可以极大的减少重叠部分计算量，尤其是当重叠部分比较大的时候，效果格外明显。滑动窗口主要解决的是连续定长子数组的问题，但是有一些非定长的也可以通过滑动窗口的思想来解决。

当我们移动窗口时只需要排除移除的一个数据，在加入移入的一个数据，窗口内其它数据是不需要做出改变的。

非定长一般需要通过加入内层循环来解决。

/**

 * 力扣209 长度最小的子数组

 * @author zhj

 */

public class Test209 {


    public static void main(String[] args) {

        int[] nums = {2,3,1,2,4,3};

        System.out.println(mumsLength(nums, 7));

    }


    private static int mumsLength(int[] nums, int sum) {

        if (nums == null || nums.length == 0) {

            return 0;

        }

        int res = nums.length + 1;

        int total = 0;

        int i = 0;

        int j = 0;

        while (j < nums.length) {

            total = total + nums[j];

            j++;

            while (total >= sum) {

                res = res < j-i ? res : j-i;

                total = total - nums[i];

                i = i + 1;

            }

        }

        if (res == nums.length + 1) {

            return 0;

        }

        return res;

    }

}

6 递归

一些复杂的问题，我们往往可以通过递归去简化。

特点：自己调自己，根据特点条件可以返回，不会陷入死循环。

递归的四个要素：

• 参数
• 返回值
• 终止条件
• 递归拆解

经典问题斐波那契数列

0，1，1，2，3，5... f(0) = 0 f(1) = 1 f(n) = f(n-1) + f(n-2)

int recursion(int n) {

    if (n < 2) {

        return n == 1 ? 1 : 0;

    }

    return recursion(n-1) + recursion(n-2);

}

7 高阶算法

除了上边一些简单的小技巧之外，还有许多高阶的算法，比如由递归引发的分治法、回溯法；还有树和图的遍历方法，深度优先遍历，广度优先遍历；还有经典的算法贪心算法、动态规划等等，本文将不做讲解，后续会单独更新在算法这一专栏中，希望大家持续关注。