数组-检查数组内是否存在和为7的倍数的子序列

一、题目描述

二、解题思路

这里首先要分辨清楚是子序列还是子数组

        原数组：[1,2,3,4,5]

        子序列：元素和元素之间相对位置保持不变，但是在原数组中不一定连续，如：[1,3,4]；

        子数组：元素元素之间保持原数组的连续关系，如：[1,2,3]；

问题中问的是子序列：

        所以我们这边可以使用回溯法，在回溯过程中判断是否存在子序列和为7的倍数（相当于穷举了所有情况）。

        设置一个标记数组hasUsed，用于判断当前元素是否被使用过，如果没有使用过纳入子序列范围计算和，然后做出判断，直到所有的子序列都尝试过。

三、代码实现

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param nums int整型一维数组 * @return int整型*/public int findRainbow (int[] nums) {// write code here//初始化hasUsed数组boolean[] hasUsed = new boolean[nums.length];for(int i=0;i<nums.length;i++){hasUsed[i]=false;}return recursiveFunc(nums,hasUsed,0)?1:0;}//注意：这里是子序列，并不是子数组，不能直接通过双层for循环来实现//通过回溯法进行查找public boolean recursiveFunc(int[] nums,boolean[] hasUsed,int nowSum){boolean resbool=false;//如果没找到则默认返回falseif(nowSum!=0&&nowSum%7==0){resbool=true;}else{for(int i=0;i<nums.length;i++){if(!hasUsed[i]){nowSum+=nums[i];hasUsed[i]=true;if(recursiveFunc(nums,hasUsed,nowSum)){resbool=true;break;}else{//这里注意，把未满足情况的当前元素要从nowSum中删除nowSum-=nums[i];hasUsed[i]=false;}}}}return resbool;}
}

四、测试用例问题

在提交测试中：这个测试用例没有通过，这个测试用例应该是返回1，在提交以后注意一下。

五、刷题链接

牛牛的彩虹数组_牛客题霸_牛客网