LeetCode:目标和
题目
给你一个整数数组 nums
和一个整数 target
。
向数组中的每个整数前添加 '+'
或 '-'
,然后串联起所有整数,可以构造一个 表达式 :
例如,nums = [2, 1]
,可以在 2
之前添加 '+'
,在 1
之前添加 '-'
,然后串联起来得到表达式 "+2-1"
。
返回可以通过上述方法构造的、运算结果等于 target
的不同 表达式 的数目。
示例 1:
1 | 输入:nums = [1,1,1,1,1], target = 3 |
示例 2:
1 | 输入:nums = [1], target = 1 |
提示:
1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 100
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/target-sum
思路
第一想到的就是笛卡尔积算法~
代码
Go
1 | package main |
执行耗时:
1 | ➜ leetcode git:(master) ✗ time go run 494.go |
官方有点 🐶,这个耗时,居然不通过,通过用例:128/138