136. 只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入:[2,2,1]
输出:1
示例 2:
输入:[4,1,2,1,2]
输出:4
哈希表
/** * @param {number[]} nums * @return {number} */ var singleNumber = function (nums) { let hash = {} for (let i = 0; i < nums.length; i++) { hash[nums[i]] ? hash[nums[i]]++ : hash[nums[i]] = 1 } for (let j in hash) { if (hash[j] === 1) { return j } } };
异或
var singleNumber = function (nums) { let ans = nums[0] for (let i = 1; i < nums.length; i++) { ans = ans ^ nums[i] } return ans };
278. 第一个错误的版本
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例 1：
输入：n = 5, bad = 4
输出：4
解释：
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。
示例 2：
输入：n = 1, bad = 1
输出：1
二分法
var solution = function (isBadVersion) { return function (n) { let left = 1, right = n while (left < right) { const mid = Math.floor(left + (right - left) / 2) if (isBadVersion(mid)) { right = mid } else { left = mid + 1 } } return left }; };
704. 二分查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入:nums = [-1,0,3,5,9,12], target = 9
输出:4
解释:9 出现在 nums 中并且下标为 4
示例 2:
输入:nums = [-1,0,3,5,9,12], target = 2
输出:-1
解释:2 不存在 nums 中因此返回 -1
提示：
你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。
二分法
var search = function (nums, target) { let low = 0, high = nums.length - 1 while (low <= high) { const mid = Math.floor((high - low) / 2) + low const num = nums[mid] if (num === target) { return mid } else if (num > target) { high = mid - 1 } else if (num < target) { low = mid + 1 } } return -1 };
findIndex
var search = function(nums, target) { return nums.findIndex(v=>v===target) };
indexOf
var search = function(nums, target) { return nums.indexOf(target) };
for循环
var search = function (nums, target) { for (let i = 0; i < nums.length; i++) { if(nums[i] === target) return i } return -1 };
35. 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
示例 4:
输入: nums = [1,3,5,6], target = 0
输出: 0
示例 5:
输入: nums = [1], target = 0
输出: 0
提示:
1 <= nums.length <= 104 -104 <= nums[i] <= 104 nums 为无重复元素的升序排列数组 -104 <= target <= 104
filter
var searchInsert = function (nums, target) { return nums.filter(v => v < target).length };
二分法
var searchInsert = function (nums, target) { let len = nums.length if (len === 0) return 0 let left = 0, right = len-1 while (left < right) { // const mid = (left + right) >> 1 const mid = Math.floor((right - left) / 2 + left) if (nums[mid] >= target) { right = mid } else if(nums[mid] < target) { left = mid + 1 } } if (nums[right] < target) { return right + 1 } return right };
977. 有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1：
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
示例 2：
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]
提示：
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 已按 非递减顺序 排序
进阶：
请你设计时间复杂度为 O(n) 的算法解决本问题
双指针
var sortedSquares = function (nums) { let i = 0, j = nums.length - 1, res = [], k = nums.length - 1 while (i <= j) { if (nums[i] * nums[i] > nums[j] * nums[j]) { res[k--] = nums[i] * nums[i++] } else { res[k--] = nums[j] * nums[j--] } } return res };
reduce+sort
var sortedSquares = function (nums) { return nums.reduce((acc, prev) => acc.concat(prev * prev), []).sort((a,b)=>a-b) };
896. 单调数列
如果数组是单调递增或单调递减的，那么它是单调的。如果对于所有 i <= j，A[i] <= A[j]，那么数组 A 是单调递增的。 如果对于所有 i <= j，A[i]> = A[j]，那么数组 A 是单调递减的。当给定的数组 A 是单调数组时返回 true，否则返回 false。
示例 1：
输入：[1,2,2,3]
输出：true
示例 2：
输入：[6,5,4,4]
输出：true
示例 3：
输入：[1,3,2]
输出：false
示例 4：
输入：[1,2,4,5]
输出：true
示例 5：
输入：[1,1,1]
输出：true
提示：
1 <= A.length <= 50000 -100000 <= A[i] <= 100000 var isMonotonic = function (nums) { let inc =true,dec = true for(let i=0;i<nums.length;i++){ if(nums[i+1]-nums[i]>0){ dec = false } if(nums[i]-nums[i+1]>0){ inc = false } } return dec || inc };
941. 有效的山脉数组
给定一个整数数组 arr，如果它是有效的山脉数组就返回 true，否则返回 false。
让我们回顾一下，如果 A 满足下述条件，那么它是一个山脉数组：
arr.length >= 3
在 0 < i < arr.length - 1 条件下，存在 i 使得：
arr[0] < arr[1] < ... arr[i-1] < arr[i]
arr[i] > arr[i+1] > ... > arr[arr.length - 1]
示例 1：
输入：arr = [2,1]
输出：false
示例 2：
输入：arr = [3,5,5]
输出：false
示例 3：
输入：arr = [0,3,2,1]
输出：true
提示：
1 <= arr.length <= 104 0 <= arr[i] <= 104
