题解 | #在旋转过的有序数组中寻找目标值#

class Solution { public: /** * * @param s string字符串 * @return int整型 */ int longestValidParentheses(string s) { // write code here //一看到子串立马想到一个常规解题套路 //即以每一个位置结尾时最长子串是多少，用额外数组arr记录 //比如arr【i】代表以i位置结尾时最长子串长度是多少 //所以只要找到arr【i】和arr【i+1】之间的关系即找到了一种依据之前的值求出当前值得方法 if(s.size()==0) return 0; int arr[1000000]={0}; int max=0; arr[0]=0; for(int i=1;i<s.size();i++) { if(s[i]=='(')//以左括号结尾的字符有效长度一定为0 arr[i]=0; else{ int index=i-arr[i-1]-1;//跳到前一个字符有效区的前一个 if(index==-1) arr[i]=0; else{ if(s[index]=='(') { arr[i]+=2; arr[i]+=arr[i-1]; if(index-1>=0) arr[i]+=arr[index-1]; } } } max=max>arr[i]?max:arr[i]; } return max; } };