1、删除倒数第 n 个节点 1.1、题目描述 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶： 你能尝试使用一趟扫描实现吗？
1.2、解题思路
此时原问题与查询链表倒数第 n 个节点的问题一致，让 sentinel 指针和 fast 指针每次走一步，当 fast == null 时，sentinel 的下一个节点就是待删除节点，此时让 sentinel.next = sentinel.next.next ，然后返回虚拟头节点的 next 即可。
1.3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 public ListNode removeNthFromEnd (ListNode head, int n) ListNode virtualHead = new ListNode(-1 ); virtualHead.next = head; ListNode fast = head; ListNode sentinel = virtualHead; for (int i = 0 ; i < n; i++) { fast = fast.next; } while (fast != null ) { fast = fast.next; sentinel = sentinel.next; } sentinel.next = sentinel.next.next; return virtualHead.next; }
2、数字在升序数组中出现的次数 2.1、题目描述 统计一个数字在升序数组 中出现的次数。
输入：[1,2,3,3,3,3,4,5],3
返回值：4
2.2、解题思路 对于升序数组，我们第一想到的就是二分查找法，在查询到第一个符合条件的 mid 后，向左向右进行查找，统计所有符合条件的个数
2.3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 public int GetNumberOfK (int [] array , int k) if (array == null || array.length == 0 ) { return 0 ; } int left = 0 ; int right = array.length - 1 ; int result = 0 ; while (left <= right) { int mid = left + (right - left) / 2 ; if (k < array[mid]) { right = mid - 1 ; } else if (k > array[mid]) { left = mid + 1 ; } else { int index = mid; while (index >= 0 && array[index] == k) { result++; index--; } index = mid + 1 ; while (index <= array.length - 1 && array[index] == k) { result++; index++; } return result; } } return 0 ; }
3、验证 IP 地址 3.1、题目描述 编写一个函数来验证输入的字符串是否是有效的 IPv4 或 IPv6 地址
3.2、解题思路 一个合法的 IPv4 地址可以根据 . 分割为 4 组，且分割后每组元素都不为空，且每组的长度均 <= 3，每组大小在 0 - 255 之间，每组不包含前导 0 ，除非本身为 0
一个合法的 IPv4 地址可以根据 : 分割为 8 组，且分割后每组均不为空，每组长度 <= 4，组中的字符范围为：0~9 || a~f || A~F
3.3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 public String solve (String IP) if (IP == null || "" .trim().equals(IP) || IP.length() == 0 ) { return "Neither" ; } if (isIPv4(IP)) { return "IPv4" ; } else if (isIPv6(IP)) { return "IPv6" ; } else { return "Neither" ; } } private boolean isIPv6 (String ip) if (!ip.contains(":" )) { return false ; } String[] ipv6Group = ip.split(":" ); if (ipv6Group.length != 8 ) { return false ; } for (String item : ipv6Group) { if (!isIpv6Item(item)) { return false ; } } return true ; } private boolean isIpv6Item (String item) if (item == null || "" .trim().equals(item) || item.length() > 4 ) { return false ; } for (int i = 0 ; i < item.length(); i++) { if (!('0' <= item.charAt(i) && item.charAt(i) <= '9' || 'a' <= item.charAt(i) && item.charAt(i) <= 'f' || 'A' <= item.charAt(i) && item.charAt(i) <='F' )) { return false ; } } return true ; } private boolean isIPv4 (String ip) if (!ip.contains("." )) { return false ; } String[] ipv4Group = ip.split("\\." ); if (ipv4Group.length != 4 ) { return false ; } for (String item : ipv4Group) { if (!isIpv4Item(item)) { return false ; } } return true ; } private boolean isIpv4Item (String item) if (item == null || "" .trim().equals(item) || item.length() > 3 ) { return false ; } for (int i = 0 ; i < item.length(); i++) { char ch = item.charAt(i); if (!(ch >= '0' && ch <= '9' )) { return false ; } } try { int intItem = Integer.parseInt(item); if (intItem < 0 || intItem > 255 || (item.charAt(0 ) == '0' && item.length() > 1 )) { return false ; } } catch (NumberFormatException e) { return false ; } return true ; }
4、相交链表 4.1、题目描述 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交，题目数据 保证 整个链式结构中不存在环。
4.2、解题思路 先将一条链表中的数据全部 “注册” 到 HashSet 中，然后遍历另外一条链表，如果发现已经有存在的元素就直接返回该元素。
先获取两条链表的长度，设长的那条链表长度为 a ，短的那条长度为 b ，让长的那条先走 a - b 步，然后两条链表一起走，如果二者有交集，那么一定会相遇，此时返回第一个相遇节点即可。
4.3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 public ListNode getIntersectionNode (ListNode headA, ListNode headB) Set<ListNode> set = new HashSet<>(); while (headA != null ) { set.add(headA); headA = headA.next; } while (headB != null ) { if (!set.add(headB)) { return headB; } headB = headB.next; } return null ; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 public ListNode getIntersectionNode (ListNode headA, ListNode headB) if (headA == null || headB == null ) return null ; int sizeA = getLinkedListSize(headA); int sizeB = getLinkedListSize(headB); if (sizeA > sizeB) { int diff = sizeA - sizeB; for (int i = 0 ; i < diff; i++) { headA = headA.next; } } else { int diff = sizeB - sizeA; for (int i = 0 ; i < diff; i++) { headB = headB.next; } } while (headA != null && headB != null ) { if (headA == headB) return headA; headA = headA.next; headB = headB.next; } return null ; } private int getLinkedListSize (ListNode head) if (head == null ) return 0 ; if (head.next == null ) return 1 ; int size = 0 ; ListNode cur = head; while (cur != null ) { size++; cur = cur.next; } return size; }
5、插入排序链表 5.1、题目描述 对链表进行插入排序 。
5.2、解题思路 插入排序将链表分为两部分，第一部分是已经有序的链表序列，第二部分是无序的链表序列，我们对链表进行遍历，每次将链表中的一个节点加入到左边有序链表的合适位置中。
遍历链表时，如果当前节点的值小于等于它的下一个节点的值，那么我们认为这两个节点有序，直接跳过进行下一次遍历。
如果当前节点的值大于它的下一个节点的值，那么将这个节点从链表中删除，然后为这个节点找到一个合适的位置，插入
创建一个虚拟头节点，让这个头节点的 next 指针指向 head 为什么要有虚拟头节点？因为在排序过程中 head 可能被排到其他节点后面，如果有虚拟头节点，那么即使 head 在之后的排序中被排到后面，最终结果也可以使用虚拟节点获取。
创建一个 prev 节点，这个节点初始指向虚拟头节点，在每一次为节点查找插入位置时，都必须让它从虚拟头节点开始遍历 创建一个 temp 节点，这个节点用于保存要进行插入排序的节点 5.3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 public ListNode insertionSortList (ListNode head) if (head == null || head.next == null ) return head; ListNode virtualHead = new ListNode(Integer.MIN_VALUE); virtualHead.next = head; ListNode current = head; ListNode prev = null ; ListNode temp = null ; while (current != null && current.next != null ) { if (current.val <= current.next.val) { current = current.next; } else { temp = current.next; current.next = current.next.next; prev = virtualHead; while (prev.next.val <= temp.val) { prev = prev.next; } temp.next = prev.next; prev.next = temp; } } return virtualHead.next; }
6、删除数组中的重复元素 6.1、题目描述 给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
1 public int removeDuplicates (int [] nums)
其中返回值为数组中最后一个不重复元素的下标，如 int len = removeDuplicates(nums);
那么下标从 0 到 len - 1 这几个元素就是 nums 数组中不重复的所有元素
1 2 3 输入：nums = [1,1,2] 输出：2, nums = [1,2] 解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
6.2、使用双指针 我们定义两个指针，其中快指针用于扫描数组中的非重复元素，慢指针用于指向可以插入的位置
快慢指针都必须从第二个元素，即下标 1 开始，因为 nums[0] 本身是一个合法的不重复元素
当 nums[fast] == nums[fast - 1] 时，表示当前快指针指向的是一个重复元素，此时让快指针后移，慢指针不动
当 nums[fast] != nums[fast - 1] 时，表示当前快指针找到的是一个之前数组中没有出现过的新元素，此时让 nums[slow] = nums[fast] ，将当前快指针指向的这个元素插入到慢指针所指向的，可以插入的位置中。
最后返回 slow （由于 slow 指向的是可以插入的位置，那么在遍历结束后，它的位置就是最后一个不重复元素的下一个位置。）
6.3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 public int removeDuplicates (int [] nums) if (nums == null || nums.length == 0 ) return 0 ; int slow = 1 , fast = 1 ; while (fast < nums.length) { if (nums[fast - 1 ] != nums[fast]) { nums[slow++] = nums[fast]; } fast++; } return slow; }
7、矩阵置 0 7.1、题目描述 给定一个 m * n 的矩阵，如果有一个元素是 0，就把该元素所在的行和列上的元素全置为 0
7.2、解题思路 扫描两次矩阵，第一次扫描记录矩阵中 0 元素的行号和列号，并将其加入到两个 HashSet 中；第二次遍历矩阵，如果循环中的行号或列号在集合中，那么将该行和该列都置为 0
这种解法的关键思想是将第一行第一列作为标记位，用于标记该行该列是否有 0 ，我们需要对第一行第一列的元素进行判断，防止第一行第一列的元素有 0
第一行、第一列有 0 的进行标记（使用一个标记位，第一行有 0 时，将该标记位置为 true，第一列同理） 从第二行第二列开始，如果有元素为 0 ，那么将元素所在的行首和列首元素置为 0 如果第一行有 0 （标记位为 true ）那么整行都为 0，如果第一列有 0 （标记位为 true ），那么整列都为 0 7.3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 public void setZeroes (int [][] matrix) if (matrix == null || matrix.length == 0 ) return ; int rows = matrix.length; int cols = matrix[0 ].length; Set<Integer> rowSet = new HashSet<>(); Set<Integer> colSet = new HashSet<>(); for (int i = 0 ; i < rows; i++) { for (int j = 0 ; j < cols; j++) { if (matrix[i][j] == 0 ) { rowSet.add(i); colSet.add(j); } } } for (int i = 0 ; i < rows; i++) { for (int j = 0 ; j < cols; j++) { if (rowSet.contains(i) || colSet.contains(j)) { matrix[i][j] = 0 ; } } } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 public void setZeroes (int [][] matrix) boolean rowFlag = false , colFlag = false ; int rows = matrix.length; int cols = matrix[0 ].length; for (int i = 0 ; i < rows; i++) { if (matrix[i][0 ] == 0 ) { colFlag = true ; break ; } } for (int i = 0 ; i < cols; i++) { if (matrix[0 ][i] == 0 ) { rowFlag = true ; break ; } } for (int i = 1 ; i < rows; i++) { for (int j = 1 ; j < cols; j++) { if (matrix[i][j] == 0 ) { matrix[i][0 ] = matrix[0 ][j] = 0 ; } } } for (int i = 1 ; i < rows; i++) { for (int j = 1 ; j < cols; j++) { if (matrix[i][0 ] == 0 || matrix[0 ][j] == 0 ) { matrix[i][j] = 0 ; } } } if (rowFlag) { for (int i = 0 ; i < cols; i++) { matrix[0 ][i] = 0 ; } } if (colFlag) { for (int i = 1 ; i < rows; i++) { matrix[i][0 ] = 0 ; } } }
8、实现二叉树先序，中序和后序遍历 8.1、题目描述 分别按照二叉树先序，中序和后序打印所有的节点。
8.2、解题思路 分别对传入的树进行前中后序遍历，将遍历结果分别加入到 list 集合中，然后使用一个二维数组合并集合中的数据
8.3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 List<Integer> preOrderList = new ArrayList<>(); List<Integer> infixOrderList = new ArrayList<>(); List<Integer> postOrderList = new ArrayList<>(); public int [][] threeOrders (TreeNode root) { getPreOrderList(root); getInfixOrderList(root); getPostOrderList(root); int [] preResult = copyElementFromListToArray(preOrderList); int [] infixResult = copyElementFromListToArray(infixOrderList); int [] postResult = copyElementFromListToArray(postOrderList); int [][] res = new int [3 ][]; res[0 ] = preResult; res[1 ] = infixResult; res[2 ] = postResult; return res; } private void getPreOrderList (TreeNode root) if (root == null ) return ; preOrderList.add(root.val); if (root.left != null ) getPreOrderList(root.left); if (root.right != null ) getPreOrderList(root.right); } private void getInfixOrderList (TreeNode root) if (root == null ) return ; if (root.left != null ) getInfixOrderList(root.left); infixOrderList.add(root.val); if (root.right != null ) getInfixOrderList(root.right); } private void getPostOrderList (TreeNode root) if (root == null ) return ; if (root.left != null ) getPostOrderList(root.left); if (root.right != null ) getPostOrderList(root.right); postOrderList.add(root.val); } private int [] copyElementFromListToArray (List<Integer> list) { if (list == null || list.size() == 0 ) return null ; int size = list.size(); int [] result = new int [size]; for (int i = 0 ; i < size; i++) { result[i] = list.get(i); } return result; }
9、两个链表生成相加链表 9.1、题目描述 假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。
给定两个这种链表，请生成代表两个整数相加值的结果链表。
例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。
9.2、解题思路 将两个需要进行加法的链表翻转过来 对翻转后的链表进行加法计算 最后将得到的链表再次翻转，即可得到解 9.3、解题代码 这部分代码在牛客中无法通过测试用例
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 public ListNode reverseList (ListNode head) if (head == null || head.next == null ) { return head; } ListNode reverseNode = reverseList(head.next); head.next.next = head; head.next = null ; return reverseNode; } public ListNode addInList (ListNode head1, ListNode head2) head1 = reverseList(head1); head2 = reverseList(head2); ListNode result = new ListNode(Integer.MIN_VALUE); ListNode current = result; int temp = 0 ; while (head1 != null || head2 != null ) { int param1 = head1 == null ? 0 : head1.val; int param2 = head2 == null ? 0 : head2.val; int sum = param1 + param2 + temp; temp = sum / 10 ; ListNode tempNode = new ListNode(sum % 10 ); current.next = tempNode; current = current.next; if (head1 != null ) { head1 = head1.next; } if (head2 != null ) { head2 = head2.next; } } if (temp > 0 ) { current.next = new ListNode(temp); } return reverseList(result.next); }
10、反转字符串 10.1、题目描述 写出一个程序，接受一个字符串，然后输出该字符串反转后的字符串。（字符串长度不超过1000）
10.2、解题思路 使用 Java 自带的 API 进行翻转 使用双指针进行翻转 使用一个指针 i 指向字符串末尾，一个指针 j 指向新数组头部，循环将 i 指向的字符赋给 j 即可，然后让指针 i 前移，指针 j 后移。
10.3、解题代码 1 2 3 4 5 6 7 8 9 10 11 public String solve (String str) if (str == null || str.length() == 0 || "" .equals(str.trim())) return str; char [] strArray = str.toCharArray(); char [] result = new char [strArray.length]; int j = 0 ; for (int i = str.length() - 1 ; i >= 0 ; i--) { result[j++] = strArray[i]; } return new String(result); }
11、删除链表的中间节点 11.1、题目描述 给你一个不知道头节点的链表 ，实现算法来删除单链表中的中间节点(只知道指向该节点(中间节点)的指针)。
1 void deleteNode (ListNode node)
其中 node 为待删除节点
11.2、解题思路 单链表中，如果我们要删除一个节点，那么必须找到被删除节点的上一个节点，但这里没有给头节点，所以不能以普通方法解决，我们可以找到待删除节点的下一个节点 node.next ，然后将待删除节点的值赋给待删除节点 (node.val = node.next.val)，然后删去待删除节点的下一个节点。
这样就完成了对 node 节点的“删除”。
11.3、解题代码 1 2 3 4 5 6 void deleteNode (ListNode node) ListNode temp = node.next; node.val = temp.val; node.next = temp.next; temp = null ; }
12、在二叉树中找到两个节点的最近公共祖先 12.1、题目描述 给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。
注：本题保证二叉树中每个节点的val值均不相同。
给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
结点 5 和结点 1 的最近公共祖先为 3 ；结点 5 和 4 的最近公共祖先为 5 ，因为根据定义，最近公共祖先可以是自己。
12.2、解题思路 如果 root 是 o1 和 o2 的最近公共祖先，那么只可能有以下三种情况 o1 和 o2 在 root 的子树中，且分列在 root 的异侧（一个在左一个在右）
o1 = root ，且 o2 在 root 的左或右子树中
o2 = root ，且 o1 在 root 的左或右子树中
终止条件： 当越过叶子节点时，直接返回 null
当 root 等于 o1 或 o2 结点时，返回 root
递推工作 开启递归左子节点，返回值记为 left ；
开启递归右子节点，返回值记为 right ；
返回值 根据 left 和 right，可以分为以下四种情况
a. 当 left 与 right 同时为空时，说明 root 的左 / 右子树都不包含 o1,o2 ，直接返回 null
b. 当 left 与 right 同时不为空时，此时说明 o1,o2 分布在 root 的异侧，此时 root 就是最近公共祖先，返回 root
c. 当 left 为空，right 不为空时，o1 o2 都不在 root 的左子树中，此时直接返回 right
d. 当 right 为空，left 不为空时，o1 o2 都不在 root 的右子树中，此时直接返回 left
12.3、解题代码 1 2 3 4 5 6 7 8 9 10 11 public TreeNode lowestCommonAncestor (TreeNode root, TreeNode p, TreeNode q) if (root == null || p.val == root.val || q.val == root.val) return root; TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); if (left != null && right != null ) return root; if (left == null ) return right; if (right == null ) return left; return root; }
13、数组中的第K个最大元素 13.1、题目描述 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
13.2、解题思路 维护一个只有 k 个元素的最小堆 ，然后遍历数组，将数组中的元素加入到最小堆中，每次加入时我们需要进行判断：
加入元素后，如果此时最小堆中的元素个数小于 k ，那么此时不做任何事
加入元素后，如果此时最小堆中的元素个数大于 k ，那么我们依次从最小堆中 pop 出一个元素（删除堆顶元素，即去除堆中最小的元素），直到堆中元素个数为 k
在遍历完整个数组之后，此时堆中的元素就是这个数组中最大的 k 个元素，根据最小堆的特性，堆顶元素就是这些元素中最小的一个，也就是数组中第 k 大的元素。
随机取一个数（它的下标假设为 index），由于我们需要找第 k 个大的数，所以是降序排序 ，故将大于这个数的值放在左边，将小于这个数的值放在右边。 由于数组的索引是从 0 开始，所以对于一个降序排序的数组，索引为 K - 1 的元素即为第 K 大元素 在一次快速排序后，我们进行判断，如果 index = k - 1，那么证明 arr[index] 就是我们要找的数，如果 index > k - 1 ，那么证明我们要找的数在 index 的左边 ，此时向左递归查找即可 如果 index < k - 1，那么证明我们要找的数在 index 的右边 ，此时向右递归查找即可 13.3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 public int findKthLargest (int [] nums, int k) PriorityQueue<Integer> minHeap = new PriorityQueue<>(); for (int i = 0 ; i < nums.length; i++) { minHeap.add(nums[i]); if (minHeap.size() > k) { minHeap.poll(); } } return minHeap.peek(); }
14、数组中的逆序对 14.1、题目描述 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
14.2、解题思路 使用归并排序的思想来解这道题，在将多个组的元素合并到一个组时，此时用 i 指向 left ，j 指向 mid + 1，此时我们判断 i 和 j 指向元素的大小关系，如果
arr[i] <= arr[j] ，那么证明前面的元素小于等于后面的元素，构不成逆序数组 arr[i] > arr[j]，那么证明前面的元素大于后面的元素，此时构成逆序组。 使用归并排序的思想如下，在我们将一个无序组变为一个递增数组的过程中，只要存在一次交换（将前面大的元素放到小的元素后面），那么就 count++，其中 count 为逆序对个数
14.3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 public int InversePairs (int [] array) sort (array); return count; } int count = 0 ;private int [] assist;private void sort (int [] arr) if (arr == null || arr.length == 0 ) return ; assist = new int [arr.length]; sort(arr, 0 , arr.length - 1 ); } private void sort (int [] arr, int low, int high) if (low >= high) return ; int mid = low + (high - low) / 2 ; sort(arr, low, mid); sort(arr, mid + 1 , high); merge(arr, low, mid, high); } private void merge (int [] arr, int low, int mid, int high) int leftPoint = low; int assistPoint = low; int rightPoint = mid + 1 ; while (leftPoint <= mid && rightPoint <= high) { if (arr[leftPoint] < arr[rightPoint]) { assist[assistPoint++] = arr[leftPoint++]; } else { count = (count + mid - leftPoint + 1 ) % 1000000007 ; assist[assistPoint++] = arr[rightPoint++]; } } while (leftPoint <= mid) { assist[assistPoint++] = arr[leftPoint++]; } while (rightPoint <= high) { assist[assistPoint++] = arr[rightPoint++]; } for (int index = low; index <= high; index++) { arr[index] = assist[index]; } }
15、长度最小的子数组 15.1、题目描述 给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
15.2、解题思路 假设现在数组的长度为 n ，那么这道题的答案可能为 0 - n ，我们先假设长度为 1 的情况，此时遍历数组，判断其中是否有单个元素的值大于等于 target 值，如果有，直接返回 1 即可。
如果数组中没有单个元素的值大于等于 target 值，那么将子数组长度设为 2 ，查看有没有长度为 2 的子数组之和大于等于 target ，以此类推
这里以 nums = {2,3,1,2,4,3} ，target = 7 为例
定义一个指针 i 与指针 j ，程序开始时， i,j 均指向数组中的第一个元素，再定义一个值 total ，这个值初始化为 nums[i] ，表示当前指针 i 与指针 j 形成的子数组的值的总和。 当 total < target 时，我们移动 j 指针，i 不动，即扩张子数组，当 total >= target ，此时数组 {nums[i], nums[i + 1], nums[i + 2], …, nums[j]} 为问题的一个解 当 total >= target 时， j 保持不动，然后让 i 向后移，然后减去 i 的指向元素的前一个值 在这里，我们又需要判断 target 与 当前 total 的关系，如果 total < target ，那么还需要将 j 后移，然后将 nums[j] 加入到 total 中
15.3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 public int minSubArrayLen (int target, int [] nums) if (nums == null || nums.length == 0 ) return 0 ; int size = 1 ; while (size <= nums.length) { for (int i = 0 ; i < nums.length - size + 1 ; i++) { int total = 0 ; for (int j = i; j < i + size; j++) { total += nums[j]; } if (total >= target) { return size; } } size++; } return 0 ; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 public int minSubArrayLen (int target, int [] nums) if (nums == null || nums.length == 0 ) return 0 ; int left = 0 , right = 0 , result = nums.length + 1 , total = 0 ; while (right < nums.length) { total += nums[right]; right++; while (total >= target) { result = Math.min(result, right - left); total -= nums[left]; left++; } } return result == nums.length + 1 ? 0 : result; }
