题目地址
https://leetcode.com/problems/product-of-array-except-self/description/
题目描述
Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Example:
Input: [1,2,3,4]
Output: [24,12,8,6]
Note: Please solve it without division and in O(n).
Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)
思路
这道题的意思是给定一个数组,返回一个新的数组,这个数组每一项都是其他项的乘积。
符合直觉的思路是两层循环,时间复杂度是O(n^2),但是题目要求Please solve it without division and in O(n)
。
因此我们需要换一种思路,由于输出的每一项都需要用到别的元素,因此一次遍历是绝对不行的。
考虑我们先进行一次遍历, 然后维护一个数组,第i项代表前i个元素(不包括i)的乘积。
然后我们反向遍历一次,然后维护另一个数组,同样是第i项代表前i个元素(不包括i)的乘积。
有意思的是第一个数组和第二个数组的反转(reverse)做乘法(有点像向量运算)就是我们想要的运算。
其实我们进一步观察,我们不需要真的创建第二个数组(第二个数组只是做中间运算使用),而是直接修改第一个数组即可。
关键点解析
- 两次遍历, 一次正向,一次反向。
- 维护一个数组,第i项代表前i个元素(不包括i)的乘积
代码
/* * @lc app=leetcode id=238 lang=javascript * * [238] Product of Array Except Self * * https://leetcode.com/problems/product-of-array-except-self/description/ * * algorithms * Medium (53.97%) * Total Accepted: 246.5K * Total Submissions: 451.4K * Testcase Example: '[1,2,3,4]' * * Given an array nums of n integers where n > 1, return an array output such * that output[i] is equal to the product of all the elements of nums except * nums[i]. * * Example: * * * Input: [1,2,3,4] * Output: [24,12,8,6] * * * Note: Please solve it without division and in O(n). * * Follow up: * Could you solve it with constant space complexity? (The output array does * not count as extra space for the purpose of space complexity analysis.) * */ /** * @param {number[]} nums * @return {number[]} */ var productExceptSelf = function(nums) { const ret = []; for (let i = 0, temp = 1; i < nums.length; i++) { ret[i] = temp; temp *= nums[i]; } // 此时ret[i]存放的是前i个元素相乘的结果(不包含第i个) // 如果没有上面的循环的话, // ret经过下面的循环会变成ret[i]存放的是后i个元素相乘的结果(不包含第i个) // 我们的目标是ret[i]存放的所有数字相乘的结果(不包含第i个) // 因此我们只需要对于上述的循环产生的ret[i]基础上运算即可 for (let i = nums.length - 1, temp = 1; i >= 0; i--) { ret[i] *= temp; temp *= nums[i]; } return ret; };LeetCode题解1297.maximum-number-of-occurrences-of-a-substring
题目地址(1297. 子串的最大出现次数) https://leetcode-cn.com/problems/maximum-number-of-occurrences-of-a-substring 题目描述 给你一个字符串 s ,请你返回满足以下条件且出现次数最大的 任意 子串的出现次数: 子串中不同字母的数目必须小于等于 maxLetters 。 子串的…
LeetCode题解201.bitwise-and-of-numbers-range题目地址 https://leetcode.com/problems/bitwise-and-of-numbers-range/description/ 题目描述 Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbe…
LeetCode题解200.number-of-islands题目地址 https://leetcode.com/problems/number-of-islands/description/ 题目描述 Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by …
LeetCode题解152.maximum-product-subarray题目地址 https://leetcode.com/problems/maximum-product-subarray/description/ 题目描述 Given an integer array nums, find the contiguous subarray within an array (containing at least one num…
LeetCode题解1218.longest-arithmetic-subsequence-of-given-difference题目地址 https://leetcode-cn.com/problems/longest-arithmetic-subsequence-of-given-difference/ 题目描述 给你一个整数数组 arr 和一个整数 difference,请你找出 arr 中所有相邻元素之间的差等于给定 difference 的等差子序列,并返回其中最长的等差子序…