给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。
如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。
示例 1：
输入：nums = [1,2,3,4,5]
输出：true
解释：任何 i < j < k 的三元组都满足题意
var increasingTriplet = function(nums) {
let len = nums.length
let left_first = nums[len-1]
let left_second = -Infinity
for(var i=len-2;i>=0;i--){
if(nums[i]<left_second){
return true
}
nums[i]>=left_first?left_first = nums[i]:left_second = nums[i]
}
return false
};
240. 搜索二维矩阵 II
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
示例 1：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true
看了大神的题解，自己也画了图
var searchMatrix = function(matrix, target) {
if(matrix.length==0){return false}
let [bottom,left] = [0, matrix[0].length-1]
while(left>=0&&bottom<matrix.length){
if(matrix[bottom][left]>target){
left--
}else if(matrix[bottom][left]<target){
bottom++
}else{
console.log('11')
return true
}
}
console.log('22')
return false
}
matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]]
target = 5
searchMatrix(matrix, target)
除自身以外数组的乘积
除自身以外数组的乘积
给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
示例:
输入: [1,2,3,4]
输出: [24,12,8,6]
提示：题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。
说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。
进阶：
你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）
var productExceptSelf = function(nums) {
let i = 0
let len = nums.length
let resArr = []
while(i<len){
let res = 1
for(var j=0;j<len;j++){
if(j!=i){
res = res*nums[j]
}
}
resArr.push(res)
i++
}
return resArr
console.log(resArr)
};
nums=[1,2,3,4]
productExceptSelf(nums)
空间复杂度o(n),时间复杂度o(n^2)
优化时间复杂度
先算出nums[i]的左边值，再算出nums[i]的右边值，然后相乘
var productExceptSelf = function(nums) {
let len = nums.length
let resArr = []
let resArr1 = []
resArr[0] = 1
resArr1[len-1] = 1
for(var i=1;i<len;i++){
resArr[i]=resArr[i-1]*nums[i-1]
}
for(var j=len-2;j>=0;j--){
resArr1[j] = resArr1[j+1]*nums[j+1]
}
for(var m=0;m<len;m++){
resArr[m] = resArr[m]*resArr1[m]
}
return resArr
};
nums=[1,2,3,4]
// [ 1,1, 2, 6 ]
// [ 24, 12, 4, 1 ]
// [24,12,8,6]
productExceptSelf(nums)
时间复杂度o(2n) = o(n)
优化上面的空间复杂度
先算出nums[i]的左边值，nums[i]的右边值赋给一个变量，然后与左边值相乘
var productExceptSelf = function(nums) {
let len = nums.length
let resArr = []
resArr[0] = 1
for(var i=1;i<len;i++){
resArr[i]=resArr[i-1]*nums[i-1]
}
let right_count = 1//保存右边积
for(var j=len-2;j>=0;j--){
right_count = right_count*nums[j+1]
resArr[j] = right_count*resArr[j]
}
return resArr
};
