js合并两个有序升序的整数数组A和B变成一个新的数组。新数组也要有序。

### 数组的操作及相关函数 数组是一种基本的数据结构，在编程中被广泛用于存储一组具有相同类型的元素。以下是常见的数组操作及相关函数： #### 常见的数组操作 1. **连接两个数组** 使用 `concat` 方法可以将多个数组合并成一个新的数组[^1]。 ```javascript let array1 = [1, 2, 3]; let array2 = [4, 5, 6]; let combinedArray = array1.concat(array2); console.log(combinedArray); // 输出: [1, 2, 3, 4, 5, 6] ``` 2. **删除最后一个元素** 使用 `pop` 方法可以从数组中移除最后一个元素并返回该元素。 ```javascript let numbers = [1, 2, 3]; let lastElement = numbers.pop(); console.log(numbers); // 输出: [1, 2] console.log(lastElement); // 输出: 3 ``` 3. **向数组末尾添加新元素** 使用 `push` 方法可以在数组末尾添加一个或多个元素，并返回新的长度。 ```javascript let fruits = ['apple', 'banana']; let newLength = fruits.push('orange'); console.log(fruits); // 输出: ["apple", "banana", "orange"] console.log(newLength); // 输出: 3 ``` 4. **反转数组顺序** 使用 `reverse` 方法可以颠倒数组中元素的位置。 ```javascript let letters = ['a', 'b', 'c']; letters.reverse(); console.log(letters); // 输出: ["c", "b", "a"] ``` 5. **字符串拼接** 使用 `join` 方法可以将数组中的所有元素转换为一个字符串，指定分隔符可自定义输出格式。 ```javascript let words = ['hello', 'world']; let sentence = words.join(' '); console.log(sentence); // 输出: "hello world" ``` 6. **排序数组** 使用 `sort` 方法可以根据字典序对数组进行排序。 ```javascript let unsortedNumbers = [3, 1, 4, 1, 5]; let sortedNumbers = unsortedNumbers.sort((a, b) => a - b); console.log(sortedNumbers); // 输出: [1, 1, 3, 4, 5] ``` 7. **插入元素到特定位置** 使用 `splice` 方法可以修改现有数组的内容，包括删除、替换或添加元素。 ```javascript let list = ['item1', 'item2', 'item3']; list.splice(1, 0, 'newItem'); // 在索引1处插入'newItem' console.log(list); // 输出: ["item1", "newItem", "item2", "item3"] ``` 8. **通过指针访问数组** 在 C/C++ 中，可以通过指针来间接访问和操作数组[^2]。例如： ```c int arr[] = {1, 2, 3}; int *ptr = arr; printf("%d\n", *(ptr + 1)); // 输出: 2 ``` 9. **函数指针调用** 可以利用函数指针对不同功能的函数进行动态调用。 ```c void func(int x) { printf("Value is %d\n", x); } typedef void (*FuncPtr)(int); FuncPtr ptrToFunction = &func; ptrToFunction(42); // 调用了func函数 ``` 10. **复制数组内容** 不建议直接赋值整个数组，而应该使用专门的方法如 `strcpy` 或 `memcpy` 来完成数据拷贝[^3]。 #### 插入有序数组的例子 假设有一个升序排列的整数数组 `(12, 23, 26, 45, 58, 60)` 和待插入数值 `x=30`，则需找到合适位置使序列保持递增关系[^4]: ```python def insert_sorted_array(arr, value): index = next((i for i, v in enumerate(arr) if v >= value), len(arr)) result = arr[:index] + [value] + arr[index:] return result original_list = [12, 23, 26, 45, 58, 60] updated_list = insert_sorted_array(original_list, 30) print(updated_list) # 输出: [12, 23, 26, 30, 45, 58, 60] ```

### 滑动窗口算法 滑动窗口算法是一种常用于解决字符串或数组中连续子集问题的双指针技巧。它通过维护一个“窗口”来动态调整搜索范围，以优化性能并减少不必要的重复计算。 #### 实现示例：查找异位词（Anagrams） 以下代码演示了如何在 JavaScript 中使用滑动窗口算法来查找字符串 `s` 中所有 `p` 的异位词的起始索引： ```javascript function findAnagrams(s, p) { const sLen = s.length; const pLen = p.length; if (sLen < pLen) return []; const sCount = new Array(26).fill(0); const pCount = new Array(26).fill(0); for (let i = 0; i < pLen; i++) { pCount[p.charCodeAt(i) - 'a'.charCodeAt(0)]++; sCount[s.charCodeAt(i) - 'a'.charCodeAt(0)]++; } const result = []; if (sCount.toString() === pCount.toString()) { result.push(0); } for (let i = pLen; i < sLen; i++) { sCount[s.charCodeAt(i - pLen) - 'a'.charCodeAt(0)]--; sCount[s.charCodeAt(i) - 'a'.charCodeAt(0)]++; if (sCount.toString() === pCount.toString()) { result.push(i - pLen + 1); } } return result; } ``` 该实现基于固定大小的窗口，并通过字符计数比较判断当前窗口是否匹配目标字符串的字符分布[^1]。 #### 另一个应用：最小覆盖子串 下面是一个更复杂的滑动窗口应用，用于找出字符串 `s` 中包含另一个字符串 `t` 所有字符的最短子串： ```javascript var minWindow = function(s, t) { let need = new Map(), window = new Map(); for (let c of t) { need.set(c, (need.get(c) || 0) + 1); } let left = 0, right = 0, count = 0; let minLen = Infinity, start = 0; while (right < s.length) { let c = s[right]; right++; if (need.has(c)) { window.set(c, (window.get(c) || 0) + 1); if (window.get(c) === need.get(c)) { count++; } } while (count === need.size) { if (right - left < minLen) { start = left; minLen = right - left; } let d = s[left]; left++; if (need.has(d)) { if (window.get(d) === need.get(d)) { count--; } window.set(d, window.get(d) - 1); } } } return minLen === Infinity ? "" : s.substring(start, start + minLen); }; ``` 该算法通过不断扩展右指针和收缩左指针，找到满足条件的最小窗口[^2]。 --- ### 双指针算法 双指针算法是处理数组、链表等线性结构时常用的技巧，主要分为对撞指针、快慢指针和分离双指针三种形式。 #### 对撞指针 对撞指针通常用于有序数组中寻找特定组合的问题。例如，在一个升序排列的整数数组中找出两个数，使得它们的和等于某个目标值： ```javascript function twoSum(nums, target) { let left = 0; let right = nums.length - 1; while (left < right) { const sum = nums[left] + nums[right]; if (sum === target) { return [nums[left], nums[right]]; } else if (sum < target) { left++; } else { right--; } } return null; } ``` 此方法利用左右两个指针从两端向中间逼近，直到找到符合条件的解或指针相遇为止[^3]。 #### 快慢指针 快慢指针常用于链表操作，如检测环形链表是否存在环： ```javascript function hasCycle(head) { if (!head || !head.next) return false; let slow = head; let fast = head.next; while (fast && fast.next) { if (slow === fast) return true; slow = slow.next; fast = fast.next.next; } return false; } ``` 快指针每次移动两步，慢指针每次移动一步。如果存在环，则两个指针最终会相遇；否则，快指针会到达链表末尾[^4]。 #### 分离双指针 分离双指针适用于两个不同数组之间的操作，例如合并两个有序数组： ```javascript function mergeSortedArrays(arr1, arr2) { const merged = []; let i = 0, j = 0; while (i < arr1.length && j < arr2.length) { if (arr1[i] <= arr2[j]) { merged.push(arr1[i]); i++; } else { merged.push(arr2[j]); j++; } } while (i < arr1.length) { merged.push(arr1[i]); i++; } while (j < arr2.length) { merged.push(arr2[j]); j++; } return merged; } ``` 这种方法利用两个独立的指针分别遍历各自的数组，并根据顺序将元素合并到新数组中[^4]。 --- ### 滑动窗口与双指针的区别 | 特点 | 滑动窗口 | 双指针 | |------|----------|--------| | **应用场景** | 适用于连续子序列问题，如查找最长无重复字符子串、最小覆盖子串等 | 适用于数组/链表中的查找、删除、合并等问题 | | **核心思想** | 维护一个可变大小的窗口，通过左右指针控制窗口的扩张与收缩 | 利用两个或多个指针进行遍历、比较或操作 | | **时间复杂度** | 一般为 O(n)，每个元素最多被访问两次 | 同样为 O(n)，但具体取决于问题需求 | | **实现方式** | 通常需要额外的数据结构（如哈希表）记录状态 | 可以直接使用指针移动，无需额外存储 | --- ###